Recursive Approach
- The goal is to break down the main problem into multiple smaller subproblems using recursion.
- 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’.
-
Let’s look at the functioning of this LCS() function
- If either of ‘N’, ‘M’, ‘K’ becomes 0, We’ll return zero return 0.
-
Now compare A[M - 1], B[N - 1] and C[P - 1],
- If they are the same, return 1 + LCS(A, B, C, M-1, N-1, P-1).
- 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;
}
You can also try this code with Online C++ Compiler
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
- 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].
- Set the table's initial value to -1.
- 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.'
-
The helper function's algorithm will be as follows:
- If either of ‘M’, ‘N’, ‘K’ equals zero, return 0.
- 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].
-
Now compare A[M - 1], B[N - 1], and C[K - 1];
- if they are equal, update DP[M][N][K] to 1 + findLcs (A, B, C, N - 1, M - 1, K - 1).
- 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).)
- 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;
}
You can also try this code with Online C++ Compiler
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
- 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.
- 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].
-
Algorithm for filling the 'DP':
- Loop 1: For i = 1 to 'M':
- Loop 2: For j = 1 to 'N':
-
Loop 3: For t = 1 to ‘K’:
-
if(A[i] == B[j] == C[t] ),
- 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;
}
You can also try this code with Online C++ Compiler
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 -
34+ registered 
