# 1048. Longest String Chain

[Link](https://leetcode.com/problems/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: ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: one of the longest word chain is "a","ba","bda","bdca".
```

**Note:**

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

#### Solution

```java
  public int longestStrChain(String[] words) {
        int max = 1;
        int N = words.length;
        Map<String, Integer> map = new HashMap<>();
        Arrays.sort(words, (w1, w2)-> w1.length() - w2.length());
        for(int i = 0; i < N; i++){
           map.put(words[i], 1);

           for(int j = 0; j < words[i].length(); j++){
                String newWord = words[i].substring(0, j) + words[i].substring(j+1);
                map.put(words[i], Math.max(map.get(words[i]),
                                           map.getOrDefault(newWord, 0) + 1 ));
           }
           max = Math.max(max, map.get(words[i]));
        }
        return max;
    }
```
