> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/dynamic-programming/1048.-longest-string-chain.md).

# 1048. Longest String Chain

![](/files/CExTsJtBvK3pxO2bjcGY)

![](/files/a3XSEfR4EIZBLORgYtQJ)

<https://leetcode.com/problems/longest-string-chain/discuss/1543825/Java-DP-with-HashMap-clear-explanation>

### DP with HashMap

#### 1. from shortest words, words\[] sort by length

#### 2. dp with hashmap

```
because this question want find longest word chain with predecessor, 
so we can think about use map to store word predecessor
```

#### 3. for each word

```
ex1
Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4

"a",       the longest word chain: 1, save to map(a, 1)
"b",       the longest word chain: 1, save to map(b, 1)

"ba", => 
we can remove one char to find in map, is there a predecessor, 

so remove b => map.get(a) = 1, so 1 + 1(remove one char) = 2
remove a  => map.get(b) = 1, so 1 + 1 = 2, store map<ba, 2>

"bca",  remove c, get(ba) = 2 + 1 = 3 
"bda",  remove d, get(ba) = 2 + 1 = 3 
"bdca", remove d, get(bca) = 3 + 1 = 4

ans is 4
```

#### why count = Math.max(count, map.get(findStr)+1); needs do max?

```
["bdca","bda","ca","dca","a"]
ans: 4

a, ca, dca, bda, bdca

a 1
ca 2
dca 3
bda 1
bdca 4 => bda =>(1+1), dca(3+1), so when cal count, should take max count result

if (map.containsKey(findStr)) {
    count = Math.max(count, map.get(findStr)+1);
}
```

time: O(nlogn + n\*w), n is words\[i].length (1\~16) , w is word length(1\~1000)&#x20;

space: O(n)

```java
class Solution {
    public int longestStrChain(String[] words) {
        int res = 0;
        
        // dp means when word = xxx, word's the longest predecessor number: 
        // map(word, the longest predecessor number)
        Map<String, Integer> map = new HashMap<>(); 
        
        // notice this sort by string len
        // needs sort asc, because start from short one is easy to make longer word chain
        Arrays.sort(words, (a, b) -> a.length() - b.length());
        
        for (String word : words) {
            int curr = 1; // init each word's predecessor is 1
            for (int i = 0; i < word.length(); i++) {
                StringBuilder sb = new StringBuilder(word); 
                
                // remove one char in word, to find if there is a larger predecessor in map
                String next = sb.deleteCharAt(i).toString(); 
                
                if (map.containsKey(next)) {
                    curr = Math.max(map.get(next) + 1,  curr);
                }
            }
            map.put(word, curr); // update the map(word, longer value)
            res = Math.max(res, curr); // keep longer value
        }
        return res;
    }
}
```