#include <bits/stdc++.h>
using namespace std;
class Solution {

    int isPred(string &pred,string &suc) {
        if((pred.length()+1)!=suc.length()) return 0; //False

        int misCount=0;
        int i=0;
        int j=0;
        int l1 = pred.length();
        int l2 = suc.length();
        while((i<l1)&&(j<l2)) {
            if(pred[i]!=suc[j]) {
                 misCount+=1;
                 j+=1;
            }
            if(misCount>1) return 0;
            i+=1;
            j+=1;

        }
        return 1;
    }

public:
   static bool comparex(string &a,string &b) {
    return (a.length()<b.length());
}

    int longestStrChain(vector<string>& words) {
        int n = words.size();

        sort(words.begin(),words.end(),comparex);

        vector<int> dp(n+2,1);
        int maxCount=1;
        for(int i=0;i<n;i++) {
            for(int pred=0;pred<i;pred++) {
                if((dp[pred]+1>dp[i]) && isPred(words[pred],words[i])) {
                    dp[i] = dp[pred]+1;
                    maxCount = max(maxCount,dp[i]);
                }
            }
        }

        return maxCount;
    }
};