Longest String Chain

Problem Statement

In this task, you are given an array named words that contains various words composed of lowercase English letters. Your aim is to determine the length of the longest word chain that can be formed using the given list. A word chain is a sequence where each word is a predecessor of the next one. A word wordA is considered a predecessor of wordB if wordA can be transformed into wordB by inserting exactly one letter at any position, without rearranging any of the original letters in wordA. The goal is to identify the maximum length of such a chain in the provided list of words.

Examples

Example 1

Input:

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

Output:

4

Explanation:

One of the longest word chains is ["a","ba","bda","bdca"].

Example 2

Input:

words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]

Output:

5

Explanation:

All the words can be put in a word chain ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].

Example 3

Input:

words = ["abcd","dbqca"]

Output:

1

Explanation:

The trivial word chain ["abcd"] is one of the longest word chains.
["abcd","dbqca"] is not a valid word chain because the ordering of the letters is changed.

Constraints

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 16
• words[i] only consists of lowercase English letters.

Approach and Intuition

Understanding how to form the longest word chain involves determining relationships between words based on specific transformation rules. Here's a step-by-step approach and the intuition behind solving this problem:

1. Sorting Words by Length:

   • Begin by sorting the words based on their length. This simple step helps prioritize shorter words that potentially start a word chain leading to longer versions.

2. Using Dynamic Programming:

   • Utilize a dynamic programming approach where you keep track of the longest chain that ends at each word. You do this with the help of a dictionary where the keys are words and the values are the lengths of the longest chains ending with those words.

3. Building Relationships:

   • For each word, try creating all possible words that could have led to it by removing one character at a time. This step checks for potential predecessors.
   • For each generated potential predecessor, if it exists in the list and can be used to extend an existing chain, update your dictionary's chain length for the current word.

4. Calculating the Maximum Length:

   • As you iterate and update potential chains, continually track the maximum length observed in your dictionary.

This approach steadily builds up potential sequences without needing to directly compare every word with every other word, making use of the predefined order induced by sorting and the efficient look-up capabilities of dictionaries. Each word is essentially "built" from its shorter predecessors, leading up to potentially the longest chain in the given list.

Solutions

class Solution {
public:
    int longestWordChain(vector<string>& words) {
        unordered_map<string, int> wordMap;
    
        // Sort words by length
        sort(words.begin(), words.end(), [](const string& first, const string& second) {
            return first.size() < second.size();
        });
    
        int maxLength = 1;
    
        for (const string& word : words) {
            int currentLength = 1;
            // Check all substrings obtained by removing one letter
            for (int i = 0; i < word.size(); i++) {
                string newWord = word.substr(0, i) + word.substr(i + 1);
                if (wordMap.find(newWord) != wordMap.end()) {
                    currentLength = max(currentLength, wordMap[newWord] + 1);
                }
            }
            wordMap[word] = currentLength;
            maxLength = max(maxLength, currentLength);
        }
        return maxLength;
    }
};