Longest String Chain
Medium · Dynamic Programming · Array · Hash Table · Two Pointers · String · Dynamic Programming · Sorting
Problem
Word a is a predecessor of word b when you can insert exactly one letter anywhere in a, without reordering its other letters, to get b.
A word chain is a sequence of words in which each word is a predecessor of the next. A single word is a chain of length 1.
Given an array words, return the length of the longest word chain you can build from words in the array.
Examples
Input: words = ["x","xy","zxy","zxyq","ab"] Output: 4
x → xy → zxy → zxyq adds one letter at each step; ab joins nothing.
Input: words = ["cat","dog","at"] Output: 2
"at" becomes "cat" by inserting c; "dog" links to nothing.
Input: words = ["ba","b","bca","bdca","a"] Output: 4
b → ba → bca → bdca: letters are inserted at the end, the middle and the middle again.
Constraints
- 1 <= len(words) <= 1000
- 1 <= len(words[i]) <= 16
- words[i] consists of lowercase English letters.
Approaches
- Baseline: compare every pair of words — time O(n² · L), space O(n)
Follow-up
The same "sort, then extend the best chain ending at a smaller item" shape solves other chain questions: numbers that divide each other, and envelopes that nest. Both are use cases below; the envelope one also shows how a 2-D chain becomes a longest increasing subsequence.
Related problems
Start free on Cariara · Coding problems · System design studio
