Show problems as
Classic problem #1048MediumArrayHash TableTwo PointersStringDynamic ProgrammingSorting

Longest String Chain

Real-world version: Longest Chain of Grown Labels
Tracked in this browser only
Read Longest String Chain on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Labels are given as words, each a string of lowercase letters.

One label grows into another when inserting a single letter somewhere into the first, without reordering anything else, gives the second exactly.

A chain is a run of labels from the list where each grows into the next. Return the greatest number of labels a chain can hold. A single label is a chain of one.

Examples

Example 1

Input
words = ["bd", "abd", "abcd", "cd", "abdz", "x"]
Output
3

The chain "bd", "abd", "abcd", "abdz" does not work, since "abcd" does not grow into "abdz". The longest chain is "bd", "abd", "abcd", holding three labels.

Example 2

Input
words = ["ba", "ab"]
Output
1

The two labels are the same length, so neither grows into the other and a chain holds one.

Example 3

Input
words = ["a", "ab", "abc", "abcd", "abcde"]
Output
5

Each label grows into the next by adding a letter at the end, so all five form one chain.

Constraints

  • 1 <= words.length <= 1000
  • 1 <= words[i].length <= 16
  • Every entry of words consists of lowercase English letters only

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def longest_str_chain(words: list[str]) -> int:
Java
public int longestStrChain(String[] words)

More on the same topics