*This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful,* *please like**this post and/or* *upvote**my solution post on Leetcode's forums.*

####
Leetcode Problem #1048 (*Medium*): Longest String Chain

####
*Description:*

*Description:*

(*Jump to*: *Solution Idea* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

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 chainis 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:*

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

*Constraints:*

`1 <= words.length <= 1000`

`1 <= words[i].length <= 16`

`words[i]`

only consists of English lowercase letters.

####
*Idea:*

*Idea:*

(*Jump to*: *Problem Description* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

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

*Javascript Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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:*

*Python Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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:*

*Java Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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:*

*C++ Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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;
}
};
```

## Top comments (0)