LONGEST COMMON SUBSEQUENCE

CONCEPTS USED:

Dynamic programming

DIFFICULTY LEVEL:

Medium.

PROBLEM STATEMENT$($SIMPLIFIED$)$:

PrepBuddy is too good with string observations but now the Dark Lord thought to defeat PrepBuddy.
So he gave him two strings and told him to find the length of the longest common subsequence.

For Example :

> aabbcc abcc
    In this example "abcc" is the longest common subsequence.
>prep  rep
    "rep" is the longest common subsequence here.

OBSERVATION:

The question demands you to find the longest subsequence .
What is a subsequence?

A subsequence is a sequence that can be derived from another sequence by zero or more elements, without changing the order of the remaining elements. Suppose,X and Y are two sequences over a finite set of elements. We can say that Z is a common subsequence of X and Y, if Z is a subsequence of both X and Y.

SOLVING APPROACH:

Brute Force:

We need to first find the number of possible different subsequences of a string with length n with the help of best websites to learn coding., i.e., find the number of subsequences with lengths ranging from 1,2,..n-1.

Number of subsequences of length 1 are: nC1.Similarly,Number of subsequences of length 2 are: nC2 and so on and so forth.This gives –
nC0+nC1+nC2+nC3+…+nCn-1+nCn=2n.
Can you find the time complexity of this brute force?

A string of length n has 2n-1 different possible subsequences since we do not consider the subsequence with length 0. This implies that the time complexity of the brute force approach will be O(n * 2n). Note that it takes O(n) time to check if a subsequence is common to both the strings. This time complexity can be improved using dynamic programming.

You are encouraged to try on your own ,before looking at the solution.

See original problem statement here

DYMANIC PROGRAMMING:

The problem of computing their longest common subsequence, or LCS, is a standard problem and can be done in O(nm) time using dynamic programming.

Let’s define the function f. Given i and i, define f(i,j) as the length of the longest common subsequence of the strings A1,i and B1,j. Notice that A=A1,n and B=B1,m , so the length of the LCS of A and B is just f(n,m), by definition of f. Thus, our goal is to compute f(n,m).

Look at the image carefully and observe how the table is filled.

So how do we compute f(i,j) ? Let’s consider the letters Ai and Bj. There are two cases:
If Ai==Bj, then the last letter of the LCS must be Ai, because if not, then we can just always add Ai at the end to get a longer LCS. The remaining letters of the LCS must then be a common subsequence of A1,i-1 and B1,j-1 — in fact a longest common subsequence. Therefore in this case, the length of the LCS of A1,i and B1,j must be f(i,j)=1+f(i-1,j-1).

If Ai!=Bj, then Ai and Bj cannot both appear at the end of the longest common subsequence, which means either one can be ignored. If we ignore Ai , then the LCS of A1,i and B1,j becomes the LCS of A1,i-1 and B1,j, and if we ignore Bj, then the LCS becomes the LCS of A1,i and B1,j-1. The longer one of those must be the LCS of A1,i and B1,j, therefore in this case we get
f(i,j)=max(f(i-1,j),f(i,j-1)).

Pseudocode:

function f(i, j):
    if i == 0 or j == 0:
        return 0
    else if A[i] == B[j]:
        return 1 + f(i-1, j-1)
    else:
        return max(f(i-1, j), f(i, j-1))

// the answer is now f(n, m)

SOLUTIONS:

 #include <stdio.h>
     #include<stdlib.h>
     #include<string.h>
     int max(int x,int y)
    {
    if(x>y)return x;
    return y;
    }
    int main()
    {
    //write your code here
    int t;scanf("%d",&t);
    while(t--)
    {
    char s1[1005],s2[1002];
    scanf("%s%s",s1,s2);
    int dp[strlen(s1)+1][strlen(s2)+1];
    int n=strlen(s1),m=strlen(s2);
    for(int i=0;i<=n;i++)
    {
      for(int j=0;j<=m;j++)
      if(i==0||j==0)
      dp[i][j]=0;
      else
      {
        if(s1[i-1]==s2[j-1])
        dp[i][j]=dp[i-1][j-1]+1;
        else
        dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
      }
    }
    printf("%d\n",dp[n][m]);
    }

     return 0;
    }
 #include <bits/stdc++.h>
    using namespace std;

    int main()
    {
    //write your code here
    int t;cin>>t;
    while(t--)
    {
    string s1,s2;
    cin>>s1>>s2;
    int dp[s1.length()+1][s2.length()+1];
    int n=s1.length(),m=s2.length();
    for(int i=0;i<=n;i++)
    {
      for(int j=0;j<=m;j++)
      if(i==0||j==0)
      dp[i][j]=0;
      else
      {
        if(s1[i-1]==s2[j-1])
        dp[i][j]=dp[i-1][j-1]+1;
        else
        dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
      }
    }
    cout<<dp[n][m]<<"\n";
    }

     return 0;
    }
import java.util.*;
    import java.io.*;


    class LongestCommonSubsequence { 

    /* Returns length of LCS for X[0..m-1], Y[0..n-1] */
    public static int getLongestCommonSubsequence(String a, String b){
      int m = a.length();
      int n = b.length();
      int[][] dp = new int[m+1][n+1];

      for(int i=0; i<=m; i++){
        for(int j=0; j<=n; j++){
            if(i==0 || j==0){
                dp[i][j]=0;
            }else if(a.charAt(i-1)==b.charAt(j-1)){
                dp[i][j] = 1 + dp[i-1][j-1];
            }else{
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
      }

      return dp[m][n];
    }
    int max(int a, int b) 
    { 
        return (a > b) ? a : b; 
    } 
    /* Utility function to get max of 2 integers */

    public static void main(String[] args) 
    { 
      Scanner sc = new Scanner(System.in);
        int t= sc.nextInt();
        while(t-- >0 ){
       //LongestCommonSubsequence lcs = new LongestCommonSubsequence(); 
        String s1= sc.nextLine(); 
       String s2= sc.nextLine(); 

        System.out.println(getLongestCommonSubsequence(s1,s2)); }
    } 
     } 

*Space complexity: O(NM)**

Previous post COIN DIVISION
Next post BST COUNT

Leave a Reply

Your email address will not be published. Required fields are marked *