Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Longest Common Subsequence Algorithm
4.
Approach1 - Using Recursion
4.1.
Implementation
4.2.
Java
4.3.
Implementation in C++
4.4.
C++
4.5.
Time and Space Complexity
5.
Approach 2 - Using Dynamic Programming
5.1.
1. Using Top-Down Dp
5.1.1.
Implementation in Java
5.2.
C++
5.2.1.
Implementation in C++
5.3.
C++
5.3.1.
Time and Space Complexity
5.4.
2. Using Bottom-Up Dp
5.4.1.
Implementation in Java
5.5.
Java
5.5.1.
Implementation in C++
5.6.
Java
5.6.1.
 
5.6.2.
Time and Space Complexity
6.
Longest Common Subsequence Applications
7.
Frequently Asked Questions
7.1.
What is meant by longest common subsequence?
7.2.
What is the longest common subsequence measure?
7.3.
What is the longest common subsequence of an array?
7.4.
What is the longest common subsequence in linear space?
8.
Conclusion
Last Updated: Mar 27, 2024
Medium

Longest Common Subsequence

Author Raksha Jain
1 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

Today, let’s learn about a famous and commonly asked Interview Problem of Data Structure, i.e., the Longest Common Subsequence.

It is a famous and common problem that is solved using dynamic programming in its most optimized version.  

longest common subsequence

I know the Dynamic programming problem is a little tricky to understand starting, but if you go step by step in this blog, the problem will be much clear for you to solve other problems based on a similar concept.

What is Recursion

Problem Statement

Given two strings, s1 and s2, find the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some (or none) characters deleted without changing the relative order of the remaining characters. 

So, if a string is “abcde,” some of the possible subsequences of the given string are “cde,” “bc,” etc.

However, “bae” is not a valid subsequence as the relative ordering of characters is not maintained.

Example: 

Let the two strings be “acbaed” and “abcadf.” 

The longest Common Subsequence of the strings is “acad,” as this subsequence is present in both string1 and string2 and is the longest one.

So, the length of Longest Common Subsequence = size of “acad” = 4.

Problem Statement

Let's consider another example: Let the two strings be “acb”  and “dfe”. 

 

The longest Common Subsequence of the strings is “” (empty string) as it has no subsequence, which is present in both string1 and string2.

So, the length of Longest Common Subsequence = length of “” = 0.

Now, let's get started and learn various approaches to solve this problem.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Longest Common Subsequence Algorithm

There are many ways to find the longest common subsequence of two strings. These algorithms have different time and space complexities, but they solve a common problem. The following sections will discuss the different approaches to finding the longest common subsequence.

Approach1 - Using Recursion

The naive (or brute force) solution to this problem could be finding all possible configurations of different subsequences and finding the longest common subsequence possible. 

So, we maintain two indexes, i and j, one for each string and increment one by one to find the best possible solution.

Note: If any of the indices reach any of the string’s length, the longest common subsequence would be 0 as the range to find the longest common subsequence. 

Implementation

Let’s have a look at its implementation in Java:

  • Java

Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {

// Using recursive approach
public static int LCS(String s1, String s2, int i, int j){

// Base case
if (i == s1.length() || j == s2.length()) return 0;

if (s1.charAt(i) == s2.charAt(j)){
return 1 + LCS(s1, s2, i + 1, j + 1);
}

int option1 = LCS(s1, s2, i + 1, j);
int option2 = LCS(s1, s2, i, j + 1);

return Math.max(option1, option2);


public static void main (String[] args){
Scanner s = new Scanner(System.in);

// Take Input
System.out.println("Enter String1");
String s1 = s.next();

System.out.println("Enter String2");
String s2 = s.next();

int lcsans = LCS(s1,s2,0,0);

System.out.println("Longest Common Subsequence "+ lcsans);
}
}

Output:

Enter String1 acbaed
Enter String2 abcadf
Longest Common Subsequence 4

Implementation in C++

  • C++

C++

// Recursive implementation of
// Longest Common subsequence problem

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

int N, M;

// For calculating the length of the longest common subsequence

int lcs(string S, string T, int i, int j)
{
   // one or both of the strings are fully traversed


   if (i == N || j == M)
       return 0;

   // check if current characters are equal


   if (S[i] == T[j])
       // check for next character
       return (lcs(S, T, i + 1, j + 1) + 1);
   else
       // check which call has maximum value and add to length
       return max(lcs(S, T, i + 1, j), lcs(S, T, i, j + 1));
}
int main()
{
   string S = " abcde";
   string T = "acek";


   N = S.length();
   M = T.length();
   cout << "Length of longest common subsequence " << lcs(S, T, 0, 0);


   return 0;
}

 

Output:

Length of longest common subsequence 3

Time and Space Complexity

Time Complexity: O(2 ^ N), i.e., exponential as we generate and compare all the subsequences of both the strings.

Note: The total number of subsequences of a string is O(2 ^ N).

Space Complexity: O(1) as no extra space is being used.

Where ‘N’ is the length of the shortest of the two strings.

Approach 2 - Using Dynamic Programming

We could optimize the time complexity of our previous approach by maintaining a “dp array” where - dp[i][j] stores the longest common subsequence value that could be formed via considering string1 till i-th index and string2 till jth index.

Let's look at the recursive tree:

Recursion Tree

 

Since the recursive approach had a lot of overlapping subproblems, the dp array would also help us avoid that repetitive work.

 

So, let’s consider the two strings “aggtab” and “gxtxayb.” 

“-” here indicates that the value of LCS = 0 after considering the string1 and string2 till ith and jth index, respectively. 

Every time a matching character is found, the LCS value increases by one else; it remains as it is.

DP Table

1. Using Top-Down Dp

Implementation in Java

Let’s have a look at its implementation in Java 

  • C++

C++

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {

// Using Top Down dp approach
public static int LCS(String s1, String s2, int m, int n, int[][] dp){

// Base Case
if (m <= 0 || n <= 0) return 0;

// LookUp
if (dp[m][n] != 0) return dp[m][n];

// Calculating Longest Common Subsequence
if (s1.charAt(m) == s2.charAt(n))
dp[m][n] = LCS(s1, s2, m - 1, n - 1, dp) + 1;
else
dp[m][n] = Math.max(LCS(s1, s2, m - 1, n, dp), LCS(s1, s2, m, n - 1, dp));


return dp[m][n];


public static void main (String[] args){
Scanner s = new Scanner(System.in);

// Take Input
System.out.println("Enter String1");
String s1 = s.next();

System.out.println("Enter String2");
String s2 = s.next();

int m = s1.length();
int n = s2.length();

// Forming dp array
int dp[][] = new int[m][n];

int lcsans = LCS(s1, s2, m - 1, n - 1, dp);

System.out.println("Longest Common Subsequence "+ lcsans);
}
}

 

Output

Enter String1 acbaed
Enter String2 abcadf
Longest Common Subsequence 4

Implementation in C++

  • C++

C++

// Recursive implementation of
// Longest Common subsequence problem
// using memoization


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


const int max_value = 1000;


int N, M;


// For calculating the length of the longest common subsequence


int lcs(string S, string T, int i, int j, int memo[][max_value])
{
   // one or both of the strings are fully traversed


   if (i == N || j == M)
       return 0;


   // if the result for the current pair is already present in
   // the table


   if (memo[i][j] != -1)
       return memo[i][j];
// check if the current characters in both the strings are equal


   if (S[i] == T[j])
       // check for the next characters in both the strings and store the
       // calculated value in the memo table


       memo[i][j] = lcs(S, T, i + 1, j + 1, memo) + 1;
   else


       // check which call has the maximum value and store it in
       // the memo table


       memo[i][j] = max(lcs(S, T, i + 1, j, memo), lcs(S, T, i, j + 1, memo));
   return memo[i][j];
}
// Driver Code


int main()
{
   string S = "abcde";
   string T = "acek";


   N = S.length();
   M = T.length();


   // table for memoization


   int memo[N][max_value];


   // initializing memo table with -1


   for (int i = 0; i < N; i++)
       for (int j = 0; j < M; j++)
           memo[i][j] = -1;


   cout << "Length of longest common subsequence " << lcs(S, T, 0, 0, memo);
   return 0;
}

Output:

Length of longest common subsequence 3

 

Time and Space Complexity

Time Complexity: O(N ^ 2) as for each length, we are traversing from 0 to that particular length to calculate our max possible profit for the current length.

Space Complexity: O(N ^ 2) as extra space is used to store the longest common subsequence value after considering both the strings until a particular index.

Where ‘N’ is the length of the shortest of the two strings.

 

2. Using Bottom-Up Dp

Implementation in Java

Let’s have a look at its implementation in Java 

  • Java

Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {

// Using dp approach
public static int LCS(String s1, String s2){

int m = s1.length();
int n = s2.length();

// Forming dp array
int dp[][] = new int[m + 1][n + 1];

// Calculating Longest Common Subsequence
for (int i=0; i <= m; i++){
for (int j=0; j <= n; j++){
if (i == 0 || j == 0)
dp[i][j] = 0;

/*
LCS length increases by one 
when there is a character match
*/
else if (s1.charAt(i - 1) == s2.charAt(j - 1))
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[m][n];


public static void main (String[] args){
Scanner s = new Scanner(System.in);

// Take Input
System.out.println("Enter String1");
String s1 = s.next();

System.out.println("Enter String2");
String s2 = s.next();

int lcsans = LCS(s1,s2);

System.out.println("Longest Common Subsequence "+ lcsans);
}
}

 

Output:

Enter String1 acbaed
Enter String2 abcadf
Longest Common Subsequence 4

Implementation in C++

  • Java

Java

/* Dynamic Programming C++ implementation of LCS problem */
#include<bits/stdc++.h>
using namespace std;


int max(int a, int b);


/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs( char *X, char *Y, int m, int n )
{
int L[m + 1][n + 1];
int i, j;


/* Following steps build L[m+1][n+1] in
bottom up fashion. Note that L[i][j]
contains length of LCS of X[0..i-1]
and Y[0..j-1] */
for (i = 0; i <= m; i++)
{
for (j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
L[i][j] = 0;


else if (X[i - 1] == Y[j - 1])
L[i][j] = L[i - 1][j - 1] + 1;


else
L[i][j] = max(L[i - 1][j], L[i][j - 1]);
}
}


/* L[m][n] contains length of LCS
for X[0..n-1] and Y[0..m-1] */
return L[m][n];
}


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


// Driver Code
int main()
{
char X[] = "abcde";
char Y[] = "acek";


int m = strlen(X);
int n = strlen(Y);


cout << "Length of longest common subsequence "
<< lcs( X, Y, m, n );


return 0;
}

 

Output:

Length of longest common subsequence 3

 

Time and Space Complexity

Time Complexity: O(N ^ 2) as for each length, we are traversing from 0 to that particular length to calculate our max possible profit for the current length.

Space Complexity: O(N ^ 2) as extra space is used to store the longest common subsequence value after considering both the strings until a particular index.

Where ‘N’ is the length of the shortest of the two strings.

Longest Common Subsequence Applications

The following are some applications of Longest common subsequence:-

1. Version Control Systems (e.g., Git)

2. DNA sequence comparison in bioinformatics

3. Text comparison and plagiarism detection

4. Data differencing and file synchronization

5. Natural Language Processing tasks like spell checkers and similarity analysis

Frequently Asked Questions

What is meant by longest common subsequence?

The Longest Common Subsequence (LCS) is the longest sequence of elements present in two or more sequences, with the same relative order but not necessarily consecutive. It is a fundamental concept in dynamic programming and string matching algorithms.

What is the longest common subsequence measure?

A measure of similarity between two sequences, indicating the length of the longest common subsequence (LCS) they share.

What is the longest common subsequence of an array?

The longest subsequence common to two or more arrays, representing elements appearing in the same order in each array.

What is the longest common subsequence in linear space?

Efficient algorithms like the Hunt–Szymanski algorithm achieve LCS computation with linear space complexity.

Conclusion

In this blog, we learned various approaches to the Longest Common Subsequence.

  • Longest Common Subsequence is a standard recursive problem that is optimized via Dynamic Programming.
  • A subsequence of a string is a new string generated from the original string with some (or none) characters deleted without changing the relative order of the remaining characters. 
  • The optimized time complexity of this problem is O(N ^ 2) for each character at an index, and we are calculating and comparing the LCS value to the ith and jth index value of string1 and string2, respectively.
Previous article
Coin Change: Minimum Number Of Coins
Next article
Longest Common Substring
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass