1048. Longest String Chain - Explanation

1. Dynamic Programming (Top-Down)

Intuition

A word chain is built by repeatedly adding one character to form the next word. If we think backwards, each word can potentially extend to multiple shorter words by removing one character at a time. We can model this as a graph where each word points to its predecessors (words formed by deleting one character).

For each word, we try removing each character one at a time and check if that predecessor exists in our word list. If it does, we recursively find the longest chain starting from that predecessor. Memoization ensures we don't recompute chains for words we've already processed.

Algorithm

Sort words by length in descending order (optional for top-down, but helps with processing order).
Build a hash map mapping each word to its index.
Create a memoization array dp where dp[i] stores the longest chain starting from word i.
Define dfs(i) that:
- Returns cached result if available.
- Tries removing each character from words[i] to form predecessors.
- For each predecessor that exists in the word list, recursively compute its chain length.
- Returns 1 + max(chain lengths of all valid predecessors).
Call dfs for all words and return the maximum result.

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        words.sort(key=lambda w: -len(w))
        word_index = {}  # map word to index
        for i, w in enumerate(words):
            word_index[w] = i

        dp = {}  # index of word -> length of longest chain
        def dfs(i):
            if i in dp:
                return dp[i]
            res = 1
            for j in range(len(words[i])):
                w = words[i]
                pred = w[:j] + w[j+1:]
                if pred in word_index:
                    res = max(res, 1 + dfs(word_index[pred]))
            dp[i] = res
            return res

        for i in range(len(words)):
            dfs(i)
        return max(dp.values())

Time & Space Complexity

Time complexity: $O(n * m ^ 2)$
Space complexity: $O(n * m)$

Where $n$ is the number of words and $m$ is the average length of each word.

2. Dynamic Programming (Bottom-Up)

Intuition

We can build chains from shorter words to longer words. By sorting words by length, we ensure that when we process a word, all potential predecessors have already been processed. For each word, we check all previous words of length exactly one less to see if the current word can be formed by adding one character.

Algorithm

Sort words by length in ascending order.
Create a dp array where dp[i] represents the longest chain ending at word i.
For each word at index i:
- Look back at all previous words j where j < i.
- If word j has length exactly one less than word i, check if j is a predecessor of i using the isPred helper.
- Update dp[i] = max(dp[i], dp[j] + 1).
Return the maximum value in the DP array.

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        def isPred(w1, w2):
            i = 0
            for c in w2:
                if i == len(w1):
                    return True
                if w1[i] == c:
                    i += 1
            return i == len(w1)

        words.sort(key=len)
        n = len(words)
        dp = [1] * n

        for i in range(1, n):
            for j in range(i - 1, -1, -1):
                if len(words[j]) + 1 < len(words[i]):
                    break
                if len(words[j]) + 1 > len(words[i]) or not isPred(words[j], words[i]):
                    continue
                dp[i] = max(dp[i], 1 + dp[j])

        return max(dp)

Time & Space Complexity

Time complexity: $O(n ^ 2 * m)$
Space complexity: $O(n)$

Where $n$ is the number of words and $m$ is the average length of each word.

3. Dynamic Programming (Bottom-Up Optimized)

Intuition

Instead of comparing each word with all shorter words, we can generate all possible predecessors by removing one character at a time. Using a hash map to store the longest chain ending at each word, we can look up predecessors in O(1) time. This avoids the expensive pairwise comparisons of the previous approach.

Algorithm

Sort words by length in ascending order.
Create a hash map dp where dp[word] stores the longest chain ending at that word.
For each word in sorted order:
- Initialize dp[word] = 1.
- Generate all possible predecessors by removing each character.
- For each predecessor that exists in dp, update dp[word] = max(dp[word], dp[predecessor] + 1).
- Track the global maximum chain length.
Return the maximum chain length found.

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

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

        return res

Time & Space Complexity

Time complexity: $O(n * m ^ 2)$
Space complexity: $O(n * m)$

Where $n$ is the number of words and $m$ is the average length of each word.

Common Pitfalls

Forgetting to Sort by Length

The most critical step is sorting words by length before processing. Without sorting, you may try to build chains from longer words to shorter ones, which violates the chain definition. Always sort in ascending order for bottom-up DP or descending order for top-down approaches to ensure predecessors are processed before their successors.

Incorrect Predecessor Check

A common mistake is checking if two words differ by exactly one character without verifying the ordering. The predecessor must be formed by removing one character from the current word, not by adding or replacing. For example, "abc" is a predecessor of "abcd" only if you can form "abc" by deleting one character from "abcd" while maintaining the relative order of remaining characters.

Not Handling Duplicate Words

The input may contain duplicate words. Using a hash map that maps words to indices can cause issues if duplicates exist since later occurrences overwrite earlier ones. Ensure your solution handles this correctly, either by using a set of words or by taking the maximum chain length among duplicates.