LeetCode 1048: Longest String Chain

Problem Restatement

We are given an array of words.

A word wordA is a predecessor of wordB if we can insert exactly one letter anywhere in wordA to make it equal to wordB.

A word chain is a sequence of words [word_1, word_2, ..., word_k] where each word_i is a predecessor of word_{i+1}.

Return the length of the longest word chain.

The official constraints state that 1 <= words.length <= 1000, 1 <= words[i].length <= 16, and words[i] contains only lowercase English letters.

Input and Output

Function shape:

def longestStrChain(words: list[str]) -> int:
    ...

Examples

Example 1:

words = ["a", "b", "ba", "bca", "bda", "bdca"]

Chain: "a" → "ba" → "bda" → "bdca". Length 4.

Answer:

4

Key Insight

Sort words by length. Then for each word, try removing each character to get a possible predecessor. If that predecessor exists in our DP map, update the current word’s chain length.

Algorithm

1. Sort words by length.
2. dp[word] = longest chain ending at word.
3. For each word (in sorted order):
   • For each position i, form prev = word[:i] + word[i+1:].
   • dp[word] = max(dp[word], dp.get(prev, 0) + 1).
4. Return the maximum value in dp.

Correctness

Since we process words in order of increasing length, when we process word, all potential predecessors (shorter by one letter) have already been processed and their DP values computed.

For each predecessor prev of word, the chain length through prev is dp[prev] + 1. We take the maximum.

Edge Cases

• Initialize the base states explicitly; most wrong answers come from an implicit zero that should not be allowed.
• Confirm the iteration order matches the recurrence dependencies.
• For optimization DP, separate impossible states from valid states with value 0.

Complexity

Common Pitfalls

• Do not overwrite a state before all transitions that still need the old value have used it.
• Use the problem constraints to choose between full tables and compressed state.

Implementation

class Solution:
    def longestStrChain(self, words: list[str]) -> int:
        words.sort(key=len)
        dp = {}
        best = 1

        for word in words:
            dp[word] = 1
            for i in range(len(word)):
                prev = word[:i] + word[i+1:]
                if prev in dp:
                    dp[word] = max(dp[word], dp[prev] + 1)
            best = max(best, dp[word])

        return best

Testing

def run_tests():
    s = Solution()

    assert s.longestStrChain(["a","b","ba","bca","bda","bdca"]) == 4
    assert s.longestStrChain(["xbc","pcxbcf","xb","cxbc","pcxbc"]) == 5
    assert s.longestStrChain(["a"]) == 1

    print("all tests passed")

run_tests()