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

*


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://code-snippets.hbamithkumara.com/leetcode/problems/1001-1100/longest-string-chain.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.