Longest Common Subsequence

Find the longest common subsequence of the two strings.

Example

Input: X="ABCD" ,Y="BD"
Output: 2
Explanation: subsequence BD is common in both and have maximum length

Approach:

Java

public class LongestCommonSubsequence {

    static int dp[][];

    public static void main(String[] args) {

        String X = "ABCD";

        String Y = "BD";

        int n = X.length();

        int m = Y.length();

        dp = new int[n+1][m+1];

        System.out.println(LCS(X, Y, n, m));

    }

    // function to find the

    // longest commonn subsequence

    static int LCS(String X, String Y, int n, int m) {

        // base case if any string is empty

        // return 0

        if (n == 0 || m == 0)

            return 0;

        // if already calculated return

        // that value

        if (dp[n - 1][m - 1] != 0)

            return dp[n - 1][m - 1];

        // if last character is same in both

        // then

        if (X.charAt(n - 1) == Y.charAt(m - 1))

            dp[n - 1][m - 1] = 1 + LCS(X, Y, n - 1, m - 1);

        // last character is not same

        else

            dp[n - 1][m - 1] = Math.max(LCS(X, Y, n - 1, m), LCS(X, Y, n, m - 1));

        return dp[n - 1][m - 1];

    }

}

//Time Complexity:O(n*m)

C++

#include <bits/stdc++.h>

using namespace std;

int dp[1001][1001];

//function to find the 

//longest commonn subsequence

int LCS(string X,string Y,int n,int m)

{

   //base case if any string is empty

   //return 0

    if(n==0||m==0)

       return 0;

   

   //if already calculated return

   //that value

    if(dp[n-1][m-1]!=-1)

       return dp[n-1][m-1];

    //if last character is same in both

    //then

    if(X[n-1]==Y[m-1])

       dp[n-1][m-1]=1+LCS(X,Y,n-1,m-1);

   //last character is not same

    else

      dp[n-1][m-1]=max(LCS(X,Y,n-1,m),LCS(X,Y,n,m-1));

    return dp[n-1][m-1];

}

int main()

{

  string X="ABCD";

  string Y="BD";

  memset(dp,-1,sizeof(dp));

  int n=X.size(),m=Y.size();

  cout<<LCS(X,Y,n,m)<<"\n";

  return 0;

}

//Time Complexity:O(n*m)