Longest String Chain

#include <bits/stdc++.h>

int fun(int i,int j,string &s1,string &s2,vector<vector<int>>&dp1){

    if(j==-1 ) {

        return 1;

    }

    if(i==-1  && j>=0) return 0;

    if(dp1[i][j]!=-1) return dp1[i][j];

    int nt=fun(i-1,j,s1,s2,dp1);

    int t=0;

    if(s1[i]==s2[j]){

        t=fun(i-1,j-1,s1,s2,dp1);

    }

    return dp1[i][j]=(t || nt);

}

bool match(string &s1,string &s2){

    int n=s1.size();

    int m=s2.size();

    if((n-m)!=1) return false;

    vector<vector<int>>dp1(n+1,vector<int>(m+1,-1));

    return fun(n-1,m-1,s1,s2,dp1);

}

int fun1(int i,int j,vector<string>&arr,vector<vector<int>>&dp,int n){

    if(i==n) return 0;

    if(dp[i][j+1]!=-1) return dp[i][j+1];

    int nt=fun1(i+1,j,arr,dp,n);

    int t=-1e9;

    if(j==-1 or ((match(arr[i],arr[j])==true) )){

       t= 1+fun1(i+1,i,arr,dp,n);

    }

    return dp[i][j+1]=max(t,nt);

}

bool comp(string s1 ,string s2){

    return s1.length()<s2.length();

}

int longestStrChain(vector<string> &arr){

    int n=arr.size();

    sort(arr.begin(),arr.end(),comp);

    vector<vector<int>>dp(n+1,vector<int>(n+1,-1));

    return fun1(0,-1,arr,dp,n);

}

from functools import cmp_to_key

from typing import List

def cmp(a: str, b: str) -> bool:

    if len(a) < len(b):

        return -1

    return 1

#  Helper function to check if string 'A' is predecessor of 'B'.

def predecessor(a: str, b: str):

    m = len(a)

    n = len(b)

    # Check if difference between length is equal to 1.

    if (n - m != 1 or m >= n):

        return False

    i = 0

    j = 0

    # Check if 'A' is a subsequence of 'B'.

    while (i < m and j < n):

        if (a[i] == b[j]):

            i += 1

        j += 1

    return i == m

# Helper function.

def longestStrChainHelper(arr: List[str], i: int) -> int:

    # Variable to store longest chain starting from string at ARR[i].

    chainLength = 1

    for j in range(i + 1, len(arr)):

        # Check if the current string is predecessor to next string.

        if (predecessor(arr[i], arr[j])):

            # Recursive call for the j'th index.

            chainLength = max(

                chainLength, 1 + longestStrChainHelper(arr, j))

    # Update the result in 'DP' array, to avoid recomputation in future.

    return chainLength

def longestStrChain(arr: List[str]) -> int:

    n = len(arr)

    # Sort 'ARR' on basis on length of strings.

    arr = sorted(arr, key=cmp_to_key(cmp))

    # Variable to store length of longest string chain.

    length = 0

    for i in range(n):

        length = max(length, longestStrChainHelper(arr, i))

    # Finally, return the answer.

    return length

bool checkPossible(string &s1,string &s2)

{

if(s1.size()!=s2.size()+1) return false;

int first=0;

int second=0;

while(first<s1.size())

{

if(s1[first]==s2[second] && second<s2.size())

{

first++;

second++;

}

else{

first++;

}

}

if(first==s1.size() && second==s2.size())

{

return true;

}

return false;

}

static bool comp(string &s1,string &s2)

{

return s1.size()<s2.size();

}

int longestStrChain(vector<string> &arr){

int n=arr.size();

sort(arr.begin(),arr.end(),comp);

vector<int>dp(n,1);

int maxi=1;

for(int i=0;i<n;i++)

{

for(int prev=0;prev<i;prev++)

{

if(checkPossible(arr[i],arr[prev]) && 1+dp[prev]>dp[i])

{

dp[i]=1+dp[prev];

}

}

if(dp[i]>maxi)

{

maxi=dp[i];

}

}

return maxi;

}

bool check(string str1, string str2){

    if(str1.length()!=str2.length()+1) return false;

    int i=0, j=0;

    while(i<str1.length()){

        if(str1[i]==str2[j]){

            i++; j++;

        }

        else{

            i++;

        }

    }

    if(i==str1.length() and j==str2.length()) return true;

}

bool comp(string str1, string str2){

    return str1.length()<str2.length();

}

int longestStrChain(vector<string> &arr){

    int n=arr.size();

    sort(arr.begin(), arr.end(), comp);

    vector<int> dp(n, 1);

    int maxi=1;

    int lastind=0;

    for(int i=0; i<n; i++){

        for(int prev=0; prev<i; prev++){

            if(check(arr[i], arr[prev]) and 1+dp[prev]>dp[i]){

                dp[i]=1+dp[prev];

            }

        }

        if(dp[i]>maxi){

            maxi=dp[i];

        }

    }

    return maxi;

}

import java.util.*;

public class Solution {

    public static int longestStrChain(String[] arr) {

        Arrays.sort(arr,(a,b)->a.length()-b.length());

        int dp[] = new int[arr.length];  

        for(int i=0;i<arr.length;i++) dp[i]=1;

         int max=0;

        for(int i=0;i<arr.length;i++)

        {   

            for(int j=0;j<i;j++)

            {

                if(compare(arr[i],arr[j]))

                {

                    dp[i]=Math.max(dp[i],dp[j]+1);

                }

            }

            max=Math.max(max,dp[i]);

        }

        return max;

    }

    public static boolean compare(String str1 , String str2)

    {   

            if(Math.abs(str1.length()-str2.length())!=1) return false;

            if(str1.length()>str2.length())

            {

             int i=0;

             int j=0;

             while(i<str1.length() && j<str2.length())

             {

                if(str1.charAt(i)==str2.charAt(j) )

                {

                    i++;

                    j++;

                }

                else{

                    i++;

                }

             }

            if((i==str1.length() && j==str2.length()) || (i+1 == str1.length() && j== str2.length()))

             { 

                return true;

             }

            }

             return false;

    }

}

#include<bits/stdc++.h> int lcs(string X, string Y, int m, int n) {      int L[m + 1][n + 1];       for (int i = 0; i <= m; i++) {        for (int j = 0; j <= n; j++) {            if (i == 0 || j == 0)                L[i][j] = 0;            else if (X[i - 1] == Y[j - 1])                L[i][j] = L[i - 1][j - 1] + 1;            else                L[i][j] = max(L[i - 1][j], L[i][j - 1]);        }    }    return L[m][n]; }

static bool cmp(string &a, string &b) {    return a.length() <= b.length(); }

int longestStrChain(vector<string> &arr){    int n = arr.size();    sort(arr.begin(), arr.end(), cmp);    vector<int> dp(n, 1);

   int ans = 1;

   for(int curr = 1; curr < n; curr++)    {        for(int prev = 0; prev < curr; prev++)        {            if((arr[curr].length() - arr[prev].length() == 0) || (arr[curr].length() - arr[prev].length() > 1))                continue;            else               {                if(lcs(arr[curr], arr[prev], arr[curr].length(), arr[prev].length()) == arr[prev].length())                {                    if(dp[curr] < 1 + dp[prev])                    {                        dp[curr] = 1 + dp[prev];                        ans = max(ans, dp[curr]);                    }                }            }        }    }    return ans; }  

#include<bits/stdc++.h>

static bool cmp(string s,string t){

    return s.size()<t.size();

}

int longestStrChain(vector<string> &arr){

    int n=arr.size();

       unordered_map<string,int>dp;

       sort(arr.begin(),arr.end(),cmp);

       int l=1;

       for(auto x:arr){

           dp[x]=1;

           for(int i=0;i<x.size();i++){

               string p=x.substr(0,i)+x.substr(i+1);

               if(dp.find(p)!=dp.end()){

                   dp[x]=max(dp[x],dp[p]+1);

                   l=max(l,dp[x]);

               }

           }

       }

       return l;

}

bool check(string &s1, string &s2){

    if (s1.size()!=s2.size()+1){

        return false;

    }

    else{

        int first=0, second=0;

        while (first<s1.size()){

            if (s1[first]==s2[second]){

                first++, second++;

            }else{

                first++;

            }

        }

        if (first==s1.size() && second==s2.size()){

            return true;

        }else{

            return false;

        }

    }

}

bool comp(string &s1, string &s2){

    return s1.size()<s2.size();

}

int longestStrChain(vector<string> &words){

    // Write your code here.

    int n=words.size();

    vector<int> dp(n, 1);

    int maxi=1;

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

    ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);

    for (int i=1; i<n; i++){

        for (int j=0; j<i; j++){

            if (check(words[i], words[j]) && dp[i]<dp[j]+1){

                dp[i]=dp[j]+1;

            }

        }

        maxi=max(maxi, dp[i]);

    }

    return maxi;

}

#include <bits/stdc++.h> 

bool comp(string &s1,string &s2){

return s1.size()<s2.size();

}

bool compare(string s1,string s2){

    if(s1.size()!=s2.size()+1) return false;

    int first=0;

    int second=0;

    while(first<s1.size()){

        if(s1[first]==s2[second]){

            first++;

            second++;

        }

        else{

            first++;

        }

    }

    if(second==s2.size()){

        return true;

    }

    return false;

}

int longestStrChain(vector<string> &arr)

{

    int n=arr.size();

    vector<int>dp(n,1);

    int maxi=1;

  sort(arr.begin(),arr.end(),comp);

  for (int i=0;i<n;i++){

      for (int prev=0;prev<i;prev++){

            if(compare(arr[i],arr[prev]) && dp[prev]+1>dp[i]){

                dp[i]=1+dp[prev];

            }

}

if(dp[i]>maxi){

          maxi=dp[i];

      }

  }

return maxi;

}

def check(s1,s2):
    if len(s1)!=len(s2)+1:return False
    f1,f2=0,0
    while f1<len(s1):
        if f2<len(s2) and s1[f1]==s2[f2]:
            f1+=1
            f2+=1
        else:
            f1+=1

    if f1==len(s1) and f2==len(s2):return True
    return False


def longestStrChain(arr: List[str]) -> int:
    arr=sorted(arr,key=lambda x:len(x))
    Max=0
    dp=[1]*len(arr)
    for i in range(len(arr)):
        for prev in range(0,i):
            if check(arr[i],arr[prev]) and dp[prev]+1>dp[i]:
                dp[i]=dp[prev]+1
            
        Max=max(dp[i],Max)
    return Max

USING LIS technique!!!