Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Understanding the Problem
3.
Recursive Approach
3.1.
Input
3.2.
Output
3.3.
Time Complexity
3.4.
Space Complexity
4.
Memoization Approach
4.1.
Input
4.2.
Output
4.3.
Time Complexity
4.4.
Space Complexity
5.
Tabulation Approach
5.1.
Input
5.2.
Output
5.3.
Time Complexity
5.4.
Space Complexity
6.
Key Takeaways
Last Updated: Mar 27, 2024

LCS of 3 strings

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

Introduction

Strings are one of the most favorite topics of interviewers when it comes to tech interviews. Solving classical programming problems surely helps to grasp concepts. One such question is the LCS of two strings. Now LCS stands for Longest common subsequence; thus, as the name suggests, it refers to the length of the longest subsequence, which is common to both the strings.

Now we know how to calculate the LCS of two strings, but in this blog, we are going one step further. We will see how we will calculate the LCS of 3 strings. You can practice the question at the Coding Ninjas Studio and return to this blog if you feel stuck. 

Understanding the Problem

We would be given three strings, let's say A, B, C, and we have to find the length of the longest subsequence, which is common to all strings. You must be aware of but just to brush up the basics, a subsequence of a string is a new string created from the old string, with certain characters (which can be 0) removed but the relative order of the remaining characters preserved. (For example, "cde" is a subsequence of "code," but "cdo" is not).

Let’s understand the problem better by taking the following example

Let’s say we have

A=”gxtxayb”

B=”abgtab”

C=”gyaytahjb”

                                                                                                     Source: TutorialCup

The subsequence “gtab” is the longest, which is common in all three strings. Thus, our answer would be the length of “gtab”, i.e., 4.

I have got what the problem is asking, but how will I approach it?

Intuition for the problem is very similar to that of LCS of two strings. Let’s say I have three strings ‘A’,’B’,’C’.We will first check the first character of all these strings if it matches, then we will call the recursive function with substrings of these strings (e.g., A.substr(1)). If it does not match, then we will call all the remaining cases.

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

Recursive Approach

  1. The goal is to break down the main problem into multiple smaller subproblems using recursion.
  2. We'll create a recursive function called LCS(), which will accept three strings 'A', 'B', 'C' and their lengths 'M',' N', 'P' as parameters and will return the length of the longest common sub-sequence of these strings, which we'll save in the variable ‘ANSWER’.
  3. Let’s look at the functioning of this LCS() function
    1. If either of ‘N’, ‘M’, ‘K’ becomes 0, We’ll return zero return 0.
    2. Now compare A[M - 1], B[N - 1] and C[P - 1],
      1. If they are the same, return 1 + LCS(A, B, C, M-1, N-1, P-1).
      2. If they are not equal, return max(LCS(A, B, C, M-1, N, P), LCS(A, B, C, M, N-1, P), LCS(A, B, C, M, N, P-1)).


Below is the implementation of the above algorithm:

#include <iostream>
#include<algorithm>
#include<string>

using namespace std;

// This function will return the length of LCS of 'A','B' and 'C'.
int LCS(string A, string B, string C, int m, int n, int k) {
 
    // Base Case.
	if (n == 0 || m == 0 || k == 0) {
		return 0;
	}

    int answer = 0;

    // Comparing if A[m - 1], B[n - 1], C[k - 1] equal.
	if (A[m - 1] == B[n - 1] && (A[m - 1] == C[k - 1])) {
		answer= 1 + LCS(A, B, C, m - 1, n - 1, k - 1);
	}

	else {
		answer= max(max(LCS(A, B, C, m - 1, n, k), LCS(A, B, C,
          m, n - 1, k)), LCS(A, B, C, m, n, k - 1));
	}
      
      // Returning the final answer.
      return answer;

}

int main() {
    string A,B,C;
    cout << "Enter three strings : "<< endl;
    cin >> A >> B >> C;
    cout << "LCS of A, B and C is" << LCS(A, B, C, A.size(), B.size(), C.size()) << endl;
	return 0;
}

Input

code codingninjas coding

Output

Enter three strings :
LCS of A, B, and C is 3

Time Complexity

 O(3 ^ (N + M + K)), where ‘M’, ‘N’, ‘K’ are the length of the strings ‘A’, ‘B’, ‘C’.

As in the worst case we are making at max 3 ^ (N + M + K) calls to the recursive function,  

Space Complexity

O(min(N, M, K))where ‘M’, ‘N’, ‘K’ are the length of the strings ‘A’, ‘B’, ‘C’ respectively.

As we hit the base when either of ‘A’, ‘B’, ‘C’ length becomes zero This is the recursion stack space used by the algorithm.

The time complexity is exponential, and we can surely reduce it, Let’s find out how.

Memoization Approach

  1. Make a 3D dp table to store the solutions to the subproblems, where DP[i][j][k] represents the length of the longest common sub-sequence of strings A[0. . .i], B[0. . .j], and C[0. . .k].
  2. Set the table's initial value to -1.
  3. Now, we'll call a recursive function 'helper,' which takes all three strings and their lengths as arguments and returns the length of the longest common sub-sequence of these strings, which we'll save in a variable called 'answer.'
  4. The helper function's algorithm will be as follows:
    1. If either of ‘M’, ‘N’, ‘K’ equals zero, return 0.
    2. Then we'll check if the current subproblem is already is solved or not, If DP[M][N][K] ! = - 1 , return DP[M][N][K].
    3. Now compare A[M - 1], B[N - 1], and C[K - 1]; 
      1. if they are equal, update DP[M][N][K] to 1 + findLcs (A, B, C, N - 1, M - 1, K - 1).
      2. If they are not equal, update DP[M][N][K] to max(findLcs(A, B, C, N - 1, M, K), findLcs(A, B, C, N, M - 1, K), findLcs(A, B, C, N, M - 1, K), findLcs(A, B, C, N, M, K - 1).)
    4. return DP[M][N][K].


Below is the implementation of the above approach.

#include <iostream>
#include<algorithm>
#include<string>
#include<vector>

using namespace std;

// This function will return the length of LCS of 'A','B' and 'C'.
int findLCS(string A, string B, string C, int m, int n, int k, vector<vector<vector<int>>>dp){
	if (n == 0 || m == 0 || k == 0) {
		return 0;
	}

	// Apply memoization condition.
	if (dp[m][n][k] != -1) {
		return dp[n][m][k];
	}

	// Comparing if A[m - 1], B[n - 1], C[k - 1] are equal.
	if (A[m - 1] == B[n - 1] && (A[m - 1] == C[k - 1])) {
		dp[m][n][k] = 1 + findLCS(A, B, C, m - 1, n - 1, k - 1,
          dp);
	}

	else {
		dp[m][n][k] = max(max(findLCS(A, B, C, m - 1, n, k, 
          dp), findLCS(A, B, C, m, n - 1, k, dp)),findLCS(A, B,
          C, m, n, k - 1, dp));
	}
	
    // Returning the final answer.
	return dp[m][n][k];
}

int LCS(string A, string B, string C, int m, int n, int k) {

    // Declaring 3D array.
    vector<vector<vector<int>>>dp(m+2, vector<vector<int>>(n+2, vector<int>(k+2, -1)));
    return findLCS(A, B, C, n, m, k, dp);
}

int main() {
	string A,B,C;
    cout << "Enter three strings : " <<endl;
    cin >> A >> B >> C;
    cout << "LCS of A, B and C is" << LCS(A, B, C, A.size(), B.size(), C.size()) << endl;
	return 0;
} 

Input

code codingninjas coding

Output

Enter three strings :
LCS of A, B, and C is 3

Time Complexity

O(M * N * K) where ‘M’, ‘N’, ‘K’ are the length of the strings ‘A’, ‘B’, ‘C’.

As we are calculating answers for a total of M * N * K states, and calculating for each state takes O(1) time. Hence time complexity is O(M * N * K).

Space Complexity

O(M * N * K) where ‘M’, ‘N’, ‘K’ are the length of the strings ‘A’, ‘B’, ‘C’.

As we are using a DP table of size M * N * K.

Check out this problem - Shortest Common Supersequence.

Tabulation Approach

  1. At first, we will declare a 3-D DP array 'DP' of the size M * N * K, where ‘M’,’N’, ‘K’ are the length of the strings ‘A’, ‘B’, ‘C’, respectively, and initialize all the elements to 0.
  2. Now, DP[i][j][k] corresponds to the length of the longest common sub-sequence of string A[0. . .i], B[0. . .j], and C[0. . .k].
  3. Algorithm for filling the 'DP':
    1. Loop 1: For i = 1 to 'M':
    2. Loop 2: For j = 1 to 'N':
    3. Loop 3: For t = 1 to ‘K’:
      1. if(A[i] == B[j] == C[t] ),
        1. DP[i][j][t] +=DP[i - 1][j - 1][t - 1]

                      else DP[i][j][t] = max(DP[i - 1][j][t], DP[i][j - 1][t], DP[i][j][t - 1]) 

          4. Return DP[M][N][K]. 


Let’s look at the code now for a better understanding.

#include <iostream>
#include<algorithm>
#include<string>
using namespace std;

// This function will return the length of LCS of 'A','B' and 'C'.
int LCS(string A, string B, string C, int m, int n, int k) {

    // Initialising the 'DP' array.
    int dp[m + 1][n + 1][k + 1];
    
    // Now we will fill the table using the algo mentioned.
	for (int i = 0; i <= m; i++) {
		for (int j = 0; j <= n; j++) {
			for (int t = 0; t <= k; t++) {
                    
                    // Base case, if any one of them is zero.
                    if (i == 0 || j == 0 || t == 0) { 
                          dp[i][j][t] = 0;
                      }
                      
                    // Checking if the
                    else if (A[i - 1] == B[j - 1] && A[i - 1] == C[t - 1]) {
						dp[i][j][t] = 1 + dp[i - 1][j - 1][t -1];
					}

					else {
						dp[i][j][t] = max(max(dp[i - 1][j][t],
                          dp[i][j - 1][t]), dp[i][j][t - 1]);
					}
			}	
		}
	}
    
    // Returning the final answer.
	return dp[m][n][k];
}

int main() {
    string A,B,C;
    cout << "Enter three strings : " << endl;
    cin >> A >> B >> C;
    cout << "LCS of A, B and C is" << endl;
    cout << LCS(A, B, C, A.size(), B.size(), C.size()) << endl;
    return 0;

}

Input

code codingninjas coding

Output

Enter three strings :
LCS of A, B, and C is 3

Time Complexity

O(M * N * K), where ‘M’, ‘N’, ‘K’ are the length of the strings ‘A’, ‘B’, ‘C’, respectively.

As we are using three nested loops

Space Complexity

O(M * N * K), where ‘M’, ‘N’, ‘K’ are the length of the strings ‘A’, ‘B’, ‘C’, respectively.

As we are using a DP table of size m * n * k. 

Key Takeaways

Now you have understood how to find the LCS of 3 strings. We started from the recursive approach, then moved to memoization, and finally to the bottom-up approach. You must be thrilled about learning a new question. But learning never stops, and a good coder should never stop practicing. So head over to our practice platform Coding Ninjas Studio to practice top problems and many more. Till then, Happy Coding!

Recommended problems -

Previous article
Longest Repeating Subsequence
Next article
Shortest Common Supersequence
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass