Solution: Longest String Chain
Tags: algorithms, javascript, java, python
Published: 2021-05-17 11:53:19

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/longest-string-chain/discuss/1213855).*

---

#### [Leetcode Problem #1048 (*Medium*): Longest String Chain](https://leetcode.com/problems/longest-string-chain/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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`.

---

#### ***Examples:***
>
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.

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

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**.

 - _**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**._

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var longestStrChain = function(words) {
    let W = Array.from({length: 17}, _ => new Set())
    for (let i = 0; i < words.length; i++) 
        W[words[i].length].add(words[i])
    let dp = new Map(), best = 1
    for (let i = 16; i; i--) {
        if (!W[i-1].size) continue
        for (let word of W[i]) {
            let wVal = dp.get(word) || 1
            for (let j = 0; j < word.length; j++) {
                let pred = word.slice(0,j) + word.slice(j+1)
                if (W[i-1].has(pred) && wVal >= (dp.get(pred) || 1)) {
                    dp.set(pred, wVal + 1)
                    best = Math.max(best, wVal + 1)
                }
            }
        }
    }
    return best
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
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
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
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;
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
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;
    }
};
```