Longest String Chain

How it works

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.

Steps

1. Sort words by length in ascending order.
2. Create a hash map dp where dp[word] stores the longest chain ending at that word.
3. 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.
4. Return the maximum chain length found.

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.

Things to watch for

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.

from typing import List

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

class Solution {
public:
    int longestStrChain(vector<string>& words) {
        sort(words.begin(), words.end(), [](const string& a, const string& b) {
            return a.length() < b.length();
        });

        unordered_map<string, int> dp;
        int res = 0;

        for (const string& word : words) {
            dp[word] = 1;
            for (int i = 0; i < word.length(); i++) {
                string pred = word.substr(0, i) + word.substr(i + 1);
                if (dp.find(pred) != dp.end()) {
                    dp[word] = max(dp[word], dp[pred] + 1);
                }
            }
            res = max(res, dp[word]);
        }

        return res;
    }
};