The predecessor relationship drives this problem. Word A is a predecessor of word B if you can add exactly one letter to A (anywhere in it) to form B. That means B must be exactly one character longer than A, and removing the right character from B gives back A.

Adding a letter to A and removing a letter from B are two views of the same relationship. The removal view is easier to work with, because a word of length L has only L candidate predecessors (one for each character you could remove), while there are many more words you could form by inserting a letter.

The goal is to find the longest chain where each word is a predecessor of the next. This has a recursive structure: the longest chain ending at a given word equals 1 plus the longest chain ending at the best of its predecessors. A word's chain length depends only on shorter words, so the subproblems never form a cycle, which is what makes dynamic programming apply.

Key Constraints:

Intuition

Treat each word as a node in a graph, with an edge from word A to word B when A is a predecessor of B. The answer is the longest path in this graph. Run a DFS from every word, extending the chain as far as it goes, and take the maximum length.

To check whether A is a predecessor of B, B must be exactly one character longer than A, and removing one character from B must yield A. A two-pointer comparison verifies this: advance both pointers on matches, and allow exactly one extra advance in the longer word for the single inserted character.

This explores every possible chain. It is correct but slow, because it recomputes overlapping subproblems. If the word "ba" sits on multiple chains, its longest extension is recalculated on every visit.

Algorithm

Example Walkthrough

Take words = ["a", "b", "ba", "bca", "bda", "bdca"] and follow the DFS that starts at "a".

The DFS calls starting at "b", "ba", and the longer words return 3, 3, and smaller values, so the overall maximum is 4. In this trace dfs("bdca") ran three separate times. That repeated work is what the later approaches eliminate.

Code

This is correct but too slow. The repeated work comes from recomputing the longest chain for a word every time a DFS reaches it. Storing each word's result once removes that waste, which is what the next approach does with bottom-up dynamic programming.

Intuition

A predecessor is always one character shorter, so sort the words by length and process them in increasing order. By the time we reach a word, every word that could be its predecessor has already been processed, so its chain length is final. For each word, scan the earlier words of length exactly one less and, for any that is a predecessor, extend its chain.

This is the Longest Increasing Subsequence (LIS) pattern applied to strings. Instead of comparing numbers with <, words are compared with the predecessor relationship.

Algorithm

Example Walkthrough

Code

This still runs an O(L) predecessor check against every earlier word of the right length, and most of those words are not predecessors. The next approach removes those wasted checks by generating a word's predecessors directly and looking them up in a hash map.

Intuition

Rather than compare a word against every shorter word, generate its predecessors directly. For each word, remove one character at a time and check whether the resulting string is a known word.

A word of length L has exactly L candidate predecessors: remove the character at index 0, index 1, ..., index L-1. Each candidate has length L-1. If a candidate is a word we have already processed, its chain can be extended by this word.

Processing words in increasing length order means every candidate predecessor (length L-1) was handled before the current word (length L), so its chain length is already final. A hash map keyed by word stores that chain length, giving O(1) lookups instead of an O(L) comparison against each earlier word.

Algorithm

Example Walkthrough:

Code