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.

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)