1048

class Solution {
public:
    int longestStrChain(vector<string>& words) {
        unordered_map<string, int> dp;
        for(auto word: words)
            dp[word] = 1;

        sort(words.begin(), words.end(), [](auto &a, auto &b){return a.length()>b.length();});
        int ans = 1;
        for(auto word: words){
            string newWord = "";
            for(int i=0; i<word.size(); i++){
                newWord = word.substr(0,i);
                if(i+1 < word.size())
                    newWord += word.substr(i+1);
                if(dp.count(newWord)){
                    dp[newWord] = max(dp[newWord], dp[word]+1);
                    ans = max(ans, dp[newWord]);
                }
            }
        }
        return ans;
    }
};