# 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 2^{n} 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:**

- 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”). - 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”, “Toda**y**”), LCS(“Winne**r**”, “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(N ^{2})
Auxiliary Space: O(N^{2})**

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.