429. The Longest Chain of Words

Word A is a PREDECESSOR of word B when inserting exactly one character somewhere in A produces B. A chain is a sequence of words where each is a predecessor of the next. Print the length of the longest chain that can be formed from the given words.

a b ba bca bda bdca -> 4 a -> ba -> bda -> bdca

Every single word is a chain of length 1, so the answer is never 0.

The recursion looks like the longest increasing subsequence, and the state space is the interesting difference. Here the states are WORDS, not indices, and the predecessors of a word are found by deleting one character from it rather than by scanning what came before.

best(w) = 1 + max over each w with one character removed, if that word exists

There are len(w) candidates for each word, each a single lookup in a set, so the whole thing is O(total characters) lookups.

Processing words in order of INCREASING LENGTH is what makes the bottom-up version work, because a predecessor is always strictly shorter and so is already final. Sorting by length is not an optimisation here, it is the fill order.

Note that comparing every pair of words instead would be O(k^2) string comparisons, and the lookup version avoids the comparison entirely by constructing the predecessor and asking whether it exists.

Constraints - `1 ≤ k ≤ 1000` - `1 ≤ length of each word ≤ 16` - The words are distinct lowercase English letters.