class Solution {
    //Q45 striver dp
    public int longestStrChain(String[] words) {
        /* sort in ascending order find LIS with check condition 
        */
        Arrays.sort(words , (a,b)-> a.length() - b.length());   //sort in ascending order

        int n = words.length;
        int[] dp = new int[n];  //every index will store maximum LIS till that element

        int max = -1 ;
        for(int i = 0 ;i < n ; i++){
            dp[i] = 1;                                  //base case
            for(int j = 0 ; j < i ; j++){
                if(check(words[i] , words[j]) && 1+dp[j] > dp[i]){
                    dp[i] = 1+dp[j];
                }
            }
            if(dp[i] > max){
                max = dp[i];
            }
        }

        return max;
    }

    //s1 should be s2.size + 1 and check order is intact by comparing through pointers
    public boolean check(String s1 , String s2){
        if(s1.length() != s2.length() + 1 )return false;
        int first =  0;
        int second = 0;

        while(first<s1.length())
        {
            if(second<s2.length() && s1.charAt(first) == s2.charAt(second))
            {
                first++;second++;
            }
            else
            first ++;
        }

        if(first == s1.length() && second == s2.length())return true;
        return false;
    }
}