Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

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 )
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.
Full screen
Console