> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/1001-1100/longest-string-chain.md).

# 1048. Longest String Chain

### Description

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

### Constraints

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

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/longest-string-chain/)
* ProgramCreek
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** words = \["a", "b", "ba", "bca", "bda", "bdca"]

**Output:** 4

**Explanation:** One of the longest word chain is "a", "ba", "bda", "bdca".
{% endtab %}

{% tab title="Example 2" %}
**Input:** words = \["xbc", "pcxbcf", "xb", "cxbc", "pcxbc"]

**Output:** 5
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(N *(log(N+L^2))). Where N be the number of words in 
 *    the list and L be the maximum possible length of a word.
 * Space complexity : O(N). We use a map to store the length of the longest 
 *    sequence formed with each of the NN words as the end word.
 */

class Solution {
    public int longestStrChain(String[] words) {
        if(words == null || words.length < 2) {
            return words == null? 0: words.length;
        }
        Arrays.sort(words, (a, b) -> a.length()-b.length());
        Map<String, Integer> map = new HashMap();
        int longest = 0;

        for(String word: words) {
            int currLongest = 0;
            for(int i = 0; i < word.length(); i++) {
                StringBuilder prevWordSb = new StringBuilder(word);
                prevWordSb.deleteCharAt(i);
                int prevLength = 1 + map.getOrDefault(prevWordSb.toString(), 0);
                currLongest = Math.max(currLongest, prevLength);
            }
            map.put(word, currLongest);
            longest = Math.max(longest, currLongest);
        }

        return longest;
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*