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.