LCS of three strings
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

Question

LCS of three strings

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

Accepted Answer

1. It was a variation of a direct standard problem so I solved it on the go though it was of medium level.
2. The exact approach I applied is given in the link given in the problem statement.

Accepted Answer

Recursion

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’.

Space Complexity: O(1)Explanation:

O(min(n, m, k)), where n, m, k are the length of the strings A, B, C respectively.

This is the recursion stack space used by the algorithm.

Time Complexity: O(1)Explanation:

In the worst case, the time complexity is O(3^(n+m+k)), where n, m, k are the length of the strings A, B, C respectively.

Accepted Answer

Memoization

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.

Space Complexity: O(n^3)Explanation:

O(n*m*k), where n, m, k are the length of the strings A, B, C respectively.

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

Time Complexity: O(n^3)Explanation:

O(n*m*k), where n, m, k are the length of the strings A, B, C respectively.

We are calculating answer for n*m*k states and calculating for each state takes O(1) time.Hence time complexity is O(n*m*k).

Accepted Answer

Dynamic Programming

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].

Space Complexity: O(n^3)Explanation:

O(n*m*k), where n, m, k are the length of the strings A, B, C respectively.

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

Time Complexity: O(n^3)Explanation:

O(n*m*k), where n, m, k are the length of the strings A, B, C respectively.

As we are using three nested loops.

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.

Note

Input format:

Output Format

Constraints:

Top DE Shaw Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern