Question: Given two sequences, find the length of longest subsequence present in both.


A subsequence is a sequence of characters of a string generated after deleting some or all characters from that string without changing the order of remaining string characters

For example:

If we have two string “abcde” and “acgef” then the length of longest common subsequence is 3 (“ace”)

Let’s try to solve this problem with a brute force approach:

We have two strings A of size n and B of size m.

Now if we want to get LCS(A[0,….,n-1] , B[0,…..,m-1]) then we must first check if the last character of these strings is equal or not. Hence, we have two options:

  1. A[n-1] and B[m-1] are equal: If the last characters are equal then we can say that the answer is 1+LCS(A[0,….,n-2] , B[0,…..,m-2]) i.e., last character is included in the LCS string and we can now compute the LCS for A[0,….,n-2] , B[0,…..,m-2].
  2. A[n-1] and B[m-1] are not equal: If the last characters are not equal then we can proceed in two ways:
    1. Leave last character from A and compute LCS(A[0,….,n-2] , B[0,…..,m-1]).
    2. Leave last character form B and compute LCS(A[0,….,n-1] , B[0,…..,m-2]).

As we require longest length hence, answer will be maximum of the two.

Implemented code in C++:

#include<bits/stdc++.h>
using namespace std;
int LCS(string A,string B,int n,int m){
	if(n<=0 || m<=0){
		return 0;
	}
	else{
		if(A[n-1]==B[m-1]){
			return LCS(A,B,n-1,m-1)+1;
		}
		else{
			// leave last character of A
			int a = LCS(A,B,n-1,m);

			// leave last character of B
			int b = LCS(A,B,n,m-1);

			// return maximum of the two 
			return max(a,b);
		}
	}
}
int main()
{
	string A="abcdef";
	string B="accdfsw";
	int n=A.length();
	int m=B.length();
	int result = LCS(A,B,n,m);
	cout<<result<<"\n";
	return 0;
}
Output:
4

Time complexity for this algorithm is exponential O(2^n).

Let’s try to draw the recursion tree for the above recursive solution:

Recursion Tree

We can easily see that there is overlapping sub-problems. Hence, we can use dynamic programming to solve the problem.

Approach:

  1. We will create a 2-dimensional array with n+1 rows and m+1 columns lcs[n+1][m+1], where lcs[i][j] will represent the length of longest common subsequence we get using first string till ith index and second string till jth index.
  2. Now if at any point A[i]==B[j], then we can use this character in our resultant LCS and increase the length of LCS that we get till lcs[i-1][j-1] by 1.
  3. If A[i] is not equal to B[j], then we will choose the maximum from lcs[i][j-1] and lcs[i-1][j]. This step represent weather to leave the last element of A or B to get longest common subsequence.

Base Case:

The longest common subsequence of a string with any null string( a string of size 0) will always be 0.

Implemented code in C++:

#include<bits/stdc++.h>
using namespace std;
int LCS(string A,string B,int n,int m){
	int lcs[n+1][m+1];

	//lcs of any string will a null string will be 0
	for(int i=0;i<=n;i++){
		lcs[i][0]=0;
	}
	for(int i=0;i<=m;i++){
		lcs[0][i]=0;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(A[i-1]==B[j-1]){
				lcs[i][j] = 1+lcs[i-1][j-1];
			}
			else{
				lcs[i][j] = max(lcs[i-1][j] , lcs[i][j-1]);
			}
		}
	}
	return lcs[n][m];
}
int main()
{
	string A="abcdef";
	string B="accdfsw";
	int n=A.length();
	int m=B.length();
	int result = LCS(A,B,n,m);
	cout<<result<<"\n";
	return 0;
}
Output:

4

Time Complexity: O(n*m)

Space Complexity: O(n*m)

Task: Print longest common subsequence of given two strings.

If we store our action i.e., diagonal, left or up then we can easily print the LCS.

Let’s try it:

#include<bits/stdc++.h>
using namespace std;
string LCS(string A,string B,int n,int m){
	int lcs[n+1][m+1];
	char move[n+1][m+1];
	string ans;
	//lcs of any string will a null string will be 0
	for(int i=0;i<=n;i++){
		lcs[i][0]=0;
		move[i][0]='u';
	}
	for(int i=0;i<=m;i++){
		lcs[0][i]=0;
		move[0][i]='l';
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(A[i-1]==B[j-1]){
				lcs[i][j] = 1+lcs[i-1][j-1];
				move[i][j]='d';
			}
			else{
				if(lcs[i-1][j]>=lcs[i][j-1]){
					lcs[i][j]=lcs[i-1][j];
					move[i][j]='u';
				}
				else{
					lcs[i][j]=lcs[i][j-1];
					move[i][j]='l';
				}
			}
		}
	}
	// printing lcs according to our moves
	int x=n,y=m;
	while(x>=0 || y>=0){
		if(move[x][y]=='d'){
			ans = A[x-1]+ans;
			x--;
			y--;
		}
		else{
			if(move[x][y]=='l'){
				y--;
			}
			else{
				x--;
			}
		}
	}
	return ans;
}
int main()
{
	string A="abcdef";
	string B="accdfsw";
	int n=A.length();
	int m=B.length();
	string result = LCS(A,B,n,m);
	cout<<result<<"\n";
	return 0;
}
Output:

acdf

That’s all I have and thanks a lot for reading 😉 . Please let me know if any corrections/suggestions. Please do share and comments if you like the post. Thanks in advance…

Thanks Shiva Gupta for helping us to grow day by day. Shiva is expert in Data Structure and loves to solve competitive problems.


0 Comments

Leave a Reply

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

Insert math as
Block
Inline
Additional settings
Formula color
Text color
#333333
Type math using LaTeX
Preview
\({}\)
Nothing to preview
Insert