Last Updated: 6 Nov, 2020

LCS of 3 strings

Hard

Asked in companies

Solve now

Problem statement

Given three strings A, B and C, the task is to find the length of the longest common sub-sequence in all the three strings A, B and C.

A subsequence of a string is a new string generated from the original string with some characters(can be 0) deleted without changing the relative order of the remaining characters. (For eg, "cde" is a subsequence of "code" while "cdo" is not). A common subsequence of two or more strings is a subsequence that is common to all the strings.

Note

You don’t have to print anything, it has already been taken care of. Just complete the function. 
If there is no common subsequence, return 0.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of the testcase contains three space-separated positive integers n, m, k denoting the length of the strings A, B, C respectively.
The second line of the testcase contains the string A.
The third line of the testcase contains the string B.
The fourth line of the testcase contains the string C.

Output Format

For each test case, return the length of the longest common subsequence in all the three strings A, B, and C.

Constraints:

1 <= T <= 5
1 <= n, m, k <= 100
Where ‘T’ is the total number of test cases and n, m, k are the length of strings A, B, and C respectively. 

Time limit: 1 second

Solve now

Approaches

01 Approach

This problem can be solved by solving its subproblems and then combining the solutions of the solved subproblems to solve the original problem. We will do this using recursion.

Algorithm:

The idea is to use recursion to reduce the big problem into several small subproblems.
We will call a recursive function ‘helper’ that takes all the three strings and their lengths as arguments and returns us the length of the longest common sub-sequence of these strings and store it in a variable say ‘answer’.
The algorithm for the helper function will be as follows:
Int helper(A, B, C, n, m, k):
A. If n or m or k becomes 0, return 0.
B. Now compare A[n-1], B[m-1] and C[k-1],
1. If they are equal, return 1 + helper(A, B, C, n-1, m-1, k-1).
2. If they are not equal, return max(helper(A, B, C, n-1, m, k), helper(A, B, C, n, m-1, k), helper(A, B, C, n, m, k-1).)
Return the ‘answer’.

Solve now

02 Approach

We are solving this problem by solving its subproblems and then combining the solutions of those subproblems. If we analyze carefully, we will see that we are solving the same subproblems multiple times. Thus, this problem exhibits overlapping subproblems. Thus, in this approach, we will eliminate the need for solving the same subproblems again and again.

Algorithm:

The idea is to use memoization.
Create a 3D lookup table to store the solutions to the subproblems where lookUp[i][j][k] denotes the length of the longest common sub-sequence of string A[0..i], B[0..j], and C[0..k].
Initialize the table by -1.
Now, we will call a recursive function ‘helper’ that takes all the three strings and their lengths as arguments and returns us the length of the longest common sub-sequence of these strings and store it in a variable say ‘answer’.
The algorithm for the helper function will be as follows:

Int helper(A, B, C, n, m, k):

A. If n or m or k becomes 0, return 0.

B. Now check if the current problem has already been solved or not. If it is already solved, return the value stored in the lookup table.

C. That is, is lookup[n][m][k] is not equal to -1, return lookup[n][m][k].

D. Initialize a variable ‘subAns’ by 0.
E. Now compare A[n-1], B[m-1] and C[k-1],
→ If they are equal, update ‘subAns’ as 1 + helper(A, B, C, n-1, m-1, k-1).

→ If they are not equal, update ‘subAns’ as max(helper(A, B, C, n-1, m, k), helper(A, B, C, n, m-1, k), helper(A, B, C, n, m, k-1).)

→ Now, update the lookup[n][m][k] with ‘subAns’.

→ Return lookup[n][m][k].

6. Return answer.

Solve now

03 Approach

Initially, we were breaking the large problem into small problems but now, let us look at it in a different way. Let us solve the small problem first and then reach the final answer. Thus we will be using a bottom-up approach now.

Algorithm:

The idea is to create a 3-D DP of size n*m*k.
Initially, all the elements of the DP table will be 0.
Now, the value DP[i][j] means denotes the length of the longest common sub-sequence of string A[0..i], B[0..j], and C[0..k].
The detailed algorithm to fill the DP table will be as follows:
1. Loop 1: For i = 1 to N:
2. Loop 2: For j = 1 to M:
3. Loop 3: For k = 1 to K:
  if(A[i] == B[j] == C[k] ), DP[i][j][k] += DP[i-1][j-1][k-1]

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

Return DP[n][m][k].

Solve now