LCS of 3 strings

Hard
0/120
Average time to solve is 45m
16 upvotes
Asked in companies
UberD.E.Shaw

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1 
4 6 12
code 
coding 
codingninjas
Sample Output 1:
3
Explanation of sample input 1:
The longest common sub-sequence in these strings is ‘cod’ and its length is 3.
Sample Input 2:
2
6 7 8 
asfdsa
fsdgsfa
dsfsdsfh
5 5 5 
rohit
virat
rahul
Sample Output 2:
3
1
Explanation of sample input 2:
Test Case 1: 
The longest common subsequence in strings ‘asfdsa’,  ‘fsdgsfa’, ‘dsfsdsfh’ is ‘fds’ whose length is 3.    
Test Case 2: 
In ‘rohit’, ‘virat’ and ‘rahul’, ‘r’ is the only common subsequence. Hence, the answer is 1.
Hint

Can you do this recursively? Try to solve the problem by solving its subproblems first.

Approaches (3)
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:  

  1. The idea is to use recursion to reduce the big problem into several small subproblems.
  2. 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’.
  3. 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).)
  4. Return the ‘answer’.
Time Complexity

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.

Space Complexity

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. 

Code Solution
(100% EXP penalty)
LCS of 3 strings
Full screen
Console