595. Longest String Chain
You are given an array words of distinct lowercase strings.
Call word a a predecessor of word b if inserting exactly one letter somewhere into a (without reordering anything) produces b. For example, "ab" is a predecessor of "abc" and of "axb", but not of "ba" or "abcd".
A chain is a sequence of words from the array where each word is a predecessor of the next one. A single word on its own counts as a chain of length 1.
Return the number of words in the longest chain you can build.
Example 1:
Input: words = ["a", "b", "ba", "bca", "bda", "bdca"]
Output: 4
Explanation: One longest chain is "a" → "ba" → "bda" → "bdca": each step inserts exactly one letter. No chain of 5 exists, so the answer is 4.
Example 2:
Input: words = ["xbc", "pcxbcf", "xb", "cxbc", "pcxbc"]
Output: 5
Explanation: All five words line up into one chain: "xb" → "xbc" → "cxbc" → "pcxbc" → "pcxbcf".
Constraints:
- 1 ≤ words.length ≤ 1000
- 1 ≤ words[i].length ≤ 16
- words[i] consists of lowercase English letters.
- All words are distinct.
Hints:
A chain only ever moves from shorter words to longer ones (each step adds exactly one letter), so there can be no cycles. That screams dynamic programming: define best(w) = the longest chain that ends at word w, and process words shortest first so every possible predecessor is solved before it is needed.
Instead of testing w against every shorter word, flip the direction: a word of length L has only L possible predecessors — delete one character at each position. Generate those candidate strings and look them up in a hash map from word → best chain length. That is at most 16 lookups per word.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: words = ["a", "b", "ba", "bca", "bda", "bdca"]
Expected output: 4