LCS of 3 Strings

Hard
0/120
2 upvotes
Asked in companies
AmazonGoogle inc

Problem statement

Given three strings A, B and C, the task is to find the length of the longest common subsequence 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(possibly 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. 
The strings will contain the lowercase alphabets only. 
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 and the only line of each test case contains three space-separated strings A, B and C.
Output Format 
For each test case, the length of the longest common subsequence in all the three strings A, B, and C are printed.
The output of each test case is printed in a separate line.
Constraints: 
1 <= T <= 5
1 <=  | A |, | B |, | C | <= 60
Where ‘T’ is the total number of test cases and | S | represents the length of the string S.
Sample Input 1:
1 
rohit virat rahul
Sample Output 1:
1
Explanation of sample input 1:
In ‘rohit’, ‘virat’ and ‘rahul’, ‘r’ is the only common subsequence. Hence, the answer is 1.
Sample Input 2:
2
asfdsa fsdgsfa dsfsdsfh
code coder codingninjas
Sample Output 2:
3
3
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: 
The longest common subsequence in these strings is ‘cod’ and its length is 3.
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 ‘LCSHelper’ that takes all the three strings and their lengths as arguments and returns the length of the longest common subsequence of these strings and we store it in a variable say ‘answer’.
  3. The algorithm for the helper function will be as follows:
     
    int LCSHelper(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 + LCSHelper(A, B, C, N-1, M-1, K-1).
    2. If they are not equal, return max(LCSHelper(A, B, C, N-1, M, K), LCSHelper(A, B, C, N, M-1, K), LCSHelper(A, B, C, N, M, K-1).
  4. Return the ‘answer’.
Time Complexity

O(3^(N + M + K)),  where N, M, K are the lengths of the strings A, B, C respectively.

In the worst case, there will be no common subsequence present in A, B and C (i.e. the length of LCS will be 0) and each recursive call will end up in 3 recursive calls. Thus, the final time complexity will be O(3 ^ (N + M + K)).

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