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

# 29. 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: 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
```

## Solution: (DP and Hashmap)

**Approach:**\
**Starting from the longest string and removing 1 char.**

```cpp
class Solution
{
public:
    static bool comparator(string a, string b)
    {
        return a.length() < b.length();
    }
    
    int longestStrChain(vector<string> &words)
    {

        sort(words.begin(), words.end(), comparator);
        vector<int> dp(words.size(), 1);

        unordered_map<string, int> m;
        for (int i = 0; i < words.size(); i++)
        {
            m[words[i]] = i;
        }
        

        for (int i = 0; i < words.size(); i++)
        {
            string k = words[i];
            int l = words[i].length();
            if (l == 1)
            {
                continue;
            }

            for (int j = 0; j < k.length(); j++)
            {
                string str1 = k.substr(0, j);
                string str2 = k.substr(j + 1, l - j + 1);
                string res = str1 + str2;

                if (m.find(res) != m.end())
                {
                    int idx = m[res];
                    dp[i] = max(dp[i], dp[idx] + 1);
                }
            }
        }

        int res = 0;

        for (int i = 0; i < dp.size(); i++)
        {
           res = max(dp[i], res);
        }

        return res;
    }
};
```

**Time Complexity: O(n log n + n \* max(len) )**\
**Space Complexity: O(n)**