Longest String Chain

 

Given a list of words, each word consists of English lowercase letters.

Let's say word1 is a predecessor of word2 if and only if we can add exactly one letter anywhere in word1 to make it equal to word2. For example, "abc" is a predecessor of "abac".

A word chain is a sequence of words [word_1, word_2, ..., word_k] with k >= 1, where word_1 is a predecessor of word_2, word_2 is a predecessor of word_3, and so on.

Return the longest possible length of a word chain with words chosen from the given list of words.

Example 1:

Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: One of the longest word chain is "a","ba","bda","bdca".

Example 2:

Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
Output: 5

 

Constraints:

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

Approach:

A naive approach would be to check every word against every other word looking for predecessors, but that would lead to a TLE result. The first important realization that we should be able to make is that while a word may have many 26 * (word.length + 1) possible successors, it can only have word.length predecessors.

So rather than iterating from small to large words and checking every combination for a link, we can store the words in a set and only check the few possible predecessors while iterating from large to small. To aid in that, we can actually separate words into an array of sets (W) indexed by word length, so that we can directly access batches of words by their length.

(Note: As we iterate backward through W, if we find that W[i-1] is empty, we don't need to process the words in W[i], since there cannot possibly be a predecessor match.)

Then we can use a dynamic programming (DP) approach to eliminate some common subproblems. We can define a hashmap (dp) where dp[word] is the length of the longest chain ending at word found so far.

So at each word, we'll iterate through each of its predecessors (pred) and check the appropriate set in W for a match. If we find a match, we can update dp[pred] if dp[word] + 1 is better, increasing the chain by one. We should also separately keep track of the best chain length we've seen, so that once we reach the end, we can just return best.

C++ Code:

class Solution {

public:

    int longestStrChain(vector<string>& words) {

        vector<unordered_set<string>> W(17);

        for (auto word : words) 

            W[word.size()].insert(word);

        unordered_map<string, int> dp;

        int best = 1;

        for (int i = 16; i; i--) {

            if (W[i-1].empty()) continue;

            for (auto word : W[i]) {

                int wVal = dp[word] ? dp[word] : 1;

                for (int j = 0; j < word.size(); j++) {

                    string pred = word.substr(0,j) + 

                                            word.substr(j+1);

                    int pVal = dp[pred] ? dp[pred] : 1;

                    if (W[i-1].find(pred) != W[i-1].end() 

                                            && wVal >= pVal) {

                        dp[pred] = wVal + 1;

                        best = max(best, wVal + 1);

                    }

                }

            }

        }

        return best;

    }

};

Java Code:

class Solution {

    public int longestStrChain(String[] words) {

        List<Set<String>> W = new ArrayList<>(17);

        for (int i = 0; i < 17; i++)

            W.add(new HashSet<>());

        for (String word : words) 

            W.get(word.length()).add(word);

        Map<String, Integer> dp = new HashMap<>();

        int best = 1;

        for (int i = 16; i > 0; i--) {

            if (W.get(i-1).isEmpty()) continue;

            for (String word : W.get(i)) {

                int wVal = dp.getOrDefault(word, 1);

                for (int j = 0; j < word.length(); j++) {

                    String pred = word.substring(0,j) + 

                                            word.substring(j+1);

                    if (W.get(i-1).contains(pred) 

                            && wVal >= dp.getOrDefault(pred,1)) {

                        dp.put(pred, wVal + 1);

                        best = Math.max(best, wVal + 1);

                    }

                }

            }

        }

        return best;

    }

}

Python Code:

class Solution:

    def longestStrChain(self, words: List[str]) -> int:

        W = [set() for _ in range(17)]

        for word in words:

            W[len(word)].add(word)

        dp, best = defaultdict(lambda:1), 1

        for i in range(16,0,-1):

            if len(W[i-1]) == 0: continue

            for word in W[i]:

                wVal = dp[word]

                for j in range(len(word)):

                    pred = word[0:j] + word[j+1:]

                    if pred in W[i-1] and wVal >= (dp.get(pred) or 1):

                        dp[pred] = wVal + 1

                        best = max(best, wVal + 1)

        return best

• Time Complexity: O(N*M) where N is the length of words and M is the average length of the words in words.
• Space Complexity: O(N + P) where P is the number of predecessors found and stored in dp.

💻🐱‍💻If there are any suggestions / questions / mistakes in my post, please do comment below 👇