# Longest Common Subsequence

By | October 13, 2015

# Longest Common Subsequence (LCS) – Dynamic Programming

### Longest Common Subsequence Problem Statement:

Given two sequences (strings or arrays) A and B, find the length of longest subsequence present in both of them.

A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.
For example, “coe”, “ksa”, “dek”, “code”, ‘”kaksa”, .. etc are subsequences of “code kaksha”.
A string of length n has 2n different possible subsequences.

### Longest Common Subsequence Problem Example:

```A= "Code Kaksha"
B= "Cloud Kaksha is the Best"```

The length of Longest common subsequence(LCS) is 10 for “Cod Kaksha”

### Longest Common Subsequence Solution:

Video Explanation:

State of DP:

let lcs[i][j]  store the length of LCS of A[0…i-1] and B[0…j-1].

Recursion for DP:

If last characters of both sequences match (or A[m-1] == B[n-1]) then
lcs(m,n) = 1 + lcs(m-1, n-1).

If last characters of both sequences do not match (or X[m-1] != Y[n-1]) then
lcs(m, n) = MAX ( lcs(m-1,n), lcs(m, n-1)).

How it works:

1. Consider the input strings “Winner” and “Racer”. Last characters match for the strings. So length of LCS can be written as:
LCS(“Winner”, “Racer”) = 1 + LCS(“Winne”, “Race”).
2. Consider the input strings “Winner” and “Today”. Last characters do not match for the strings. So length of LCS can be written as:
LCS(“Winner”, “Today”) = MAX ( LCS(“Winne”, “Today”), LCS(“Winner”, “Toda”) ).

#### Longest Common Subsequence Solution:

Here is the working code:

```#include <bits/stdc++.h>
using namespace std;

int LCS(string A, string B)
{
int lcs[A.length()+1][B.length()+1];

for(int i=0; i<=A.length(); ++i)
for(int j=0; j<=B.length(); ++j)
{
/*One string is of length 0*/
if(i==0 || j==0)
lcs[i][j]=0;
/*When last elements are equal*/
else if(A[i-1]==B[j-1])
lcs[i][j]=lcs[i-1][j-1] + 1;
/*When last elements are not equal*/
else
lcs[i][j]= max(lcs[i-1][j] ,lcs[i][j-1] );
}
return lcs[A.length()][B.length()];
}

/* Driver program to test above function */
int main()
{
string  A= "Code Kaksha";
string  B= "Cloud Kaksha is the Best";

/*LCS is "Cod Kaksha"*/
cout<<"Length of LCS is \n"<<LCS(A, B);
return 0;
}```

Output:

```Length of LCS is
10```

Time Complexity: O(N2)
Auxiliary Space: O(N2)

An application of this algorithm is the Spoj ADFRUITS question. To understand how solution works, read the question and then refer to Spoj ADFRUITS solution.