Code Implementation

class Solution:
    def longestStrChain(self, words):
        words.sort(key=len)
        dp = {}
        max_chain = 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)
            max_chain = max(max_chain, dp[word])
        return max_chain
      

class Solution {
public:
    int longestStrChain(vector<string>& words) {
        sort(words.begin(), words.end(), [](const string &a, const string &b) {
            return a.size() < b.size();
        });
        unordered_map<string, int> dp;
        int maxChain = 1;
        for (const string &word : words) {
            dp[word] = 1;
            for (int i = 0; i < word.size(); ++i) {
                string prev = word.substr(0, i) + word.substr(i + 1);
                if (dp.count(prev)) {
                    dp[word] = max(dp[word], dp[prev] + 1);
                }
            }
            maxChain = max(maxChain, dp[word]);
        }
        return maxChain;
    }
};
      

class Solution {
    public int longestStrChain(String[] words) {
        Arrays.sort(words, (a, b) -> a.length() - b.length());
        Map<String, Integer> dp = new HashMap<>();
        int maxChain = 1;
        for (String word : words) {
            dp.put(word, 1);
            for (int i = 0; i < word.length(); i++) {
                String prev = word.substring(0, i) + word.substring(i + 1);
                if (dp.containsKey(prev)) {
                    dp.put(word, Math.max(dp.get(word), dp.get(prev) + 1));
                }
            }
            maxChain = Math.max(maxChain, dp.get(word));
        }
        return maxChain;
    }
}
      

var longestStrChain = function(words) {
    words.sort((a, b) => a.length - b.length);
    const dp = {};
    let maxChain = 1;
    for (const word of words) {
        dp[word] = 1;
        for (let i = 0; i < word.length; i++) {
            const prev = word.slice(0, i) + word.slice(i + 1);
            if (dp[prev] !== undefined) {
                dp[word] = Math.max(dp[word], dp[prev] + 1);
            }
        }
        maxChain = Math.max(maxChain, dp[word]);
    }
    return maxChain;
};
      

Problem Description

Given a list of strings words, you are to find the length of the longest possible "string chain". A string chain is a sequence of words where each word is formed by adding exactly one letter to the previous word in the chain, and all words in the chain must be present in the original list words.

For example, starting with "a", you can form "ba" by adding 'b', and from "ba" you can form "bda" by adding 'd', if all these words are in words. The goal is to find the maximum length of such a chain.

• Each word can be used only once in any chain.
• The words can be in any order in the input list.
• You must not reuse elements within the same chain.

The function should return an integer representing the length of the longest chain.

Thought Process

At first glance, this problem might suggest trying all possible sequences of words, checking if each can be formed by adding one letter at a time. However, this brute-force approach would be extremely inefficient, especially as the number of words grows.

Instead, we can notice that for any word, its possible predecessor in a chain is any word formed by removing exactly one letter. So, if we process shorter words first, we can build up the longest chain ending at each word by checking all possible predecessors.

This leads us to a dynamic programming approach: for each word, we store the length of the longest chain ending at that word, and for each word, we look for all its possible predecessors by removing each character in turn. This optimization avoids redundant calculations and leverages the structure of the problem.

Solution Approach

The algorithm can be broken down into the following steps:

1. Sort the words by length: Since a word can only be formed by adding a letter to a shorter word, we sort the words in ascending order of length.
2. Use a hash map to store chain lengths: We use a dictionary (or map) dp where dp[word] is the length of the longest chain ending at word.
3. Iterate through each word: For each word, we try removing one letter at every position to form all possible predecessor words.
4. Update chain lengths: If a predecessor exists in dp, we update the chain length for the current word to be the maximum of its current value or the predecessor's chain length plus one.
5. Track the global maximum: After processing each word, we update the global maximum chain length found so far.

This approach is efficient because it ensures that every possible predecessor has already been processed before its longer forms.

Example Walkthrough

Let's consider the sample input: ["a", "b", "ba", "bca", "bda", "bdca"]

1. After sorting by length: ["a", "b", "ba", "bca", "bda", "bdca"]
2. Start with "a" and "b": Both have no possible predecessors, so their chain length is 1.
3. Next, "ba": Remove 'b' → "a" (exists), remove 'a' → "b" (exists). So, chain length is max(1, 1) + 1 = 2.
4. For "bca": Remove 'b' → "ca" (not in list), remove 'c' → "ba" (exists, chain length 2), remove 'a' → "bc" (not in list). So, chain length is 2 + 1 = 3.
5. For "bda": Remove 'b' → "da" (not in list), remove 'd' → "ba" (exists, chain length 2), remove 'a' → "bd" (not in list). So, chain length is 2 + 1 = 3.
6. For "bdca": Remove 'b' → "dca" (not in list), remove 'd' → "bca" (exists, chain length 3), remove 'c' → "bda" (exists, chain length 3), remove 'a' → "bdc" (not in list). So, chain length is max(3, 3) + 1 = 4.
7. The final answer is 4, corresponding to the chain: "a" → "ba" → "bda" → "bdca".

Time and Space Complexity

• Brute-force approach: Would require generating all possible chains, which is exponential in the number of words, making it infeasible for large inputs.
• Optimized approach:
  
  • Sorting the words takes O(N log N), where N is the number of words.
  • For each word (N words), we check up to L possible predecessors (where L is the maximum word length), so total time is O(N * L^2) (since removing a character takes O(L)).
  • Space complexity is O(N * L) for storing the words and the dp map.

Summary

The Longest String Chain problem can be efficiently solved using dynamic programming and a hash map. By processing words from shortest to longest and building chains by removing one letter at a time, we avoid redundant calculations and ensure optimal substructure. This approach transforms a potentially exponential brute-force search into a polynomial-time solution, making it both elegant and practical for large datasets.