Longest String Chain

Medium

Sort by length, extend by one character

Problem

Return the longest chain of words where each is formed by adding one letter to the previous.

In simple words

Sort by length; each word's chain extends the best word you'd get by deleting one letter.

The idea

Sort the words by length so predecessors always come first, then for each word try deleting each character and look up the result. The best chain ending at a word is one more than the best chain ending at any valid predecessor.

The trick

Sort by length; a predecessor is always shorter.
Generate predecessors by deletion and look them up in a map.
O(n × L²) with L the word length.

←→stepspaceplay

101

1/8

Optimal

timeO(n log n)spaceO(n)

Replace the first tail ≥ x.

1// keep the smallest possible tail for each length2const tails = [];3for (const x of nums) {4  let lo = 0, hi = tails.length;5  while (lo < hi) { const m=(lo+hi)>>1;6    if (tails[m] < x) lo = m+1; else hi = m; }7  tails[lo] = x;8}9return tails.length;

Input

array: [2, 5, 3, 7, 101, 18]

Memory

num: —

Output

LIS: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: words = ["a","b","ba","bca","bda","bdca"]
Output:: 4
Explanation:: a→ba→bda→bdca is a chain of 4.

Example 2

Input:: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
Output:: 5
Explanation:: A chain of length 5.

Example 3

Input:: words = ["abcd","dbqca"]
Output:: 1
Explanation:: No word extends another → 1.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.