New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

LCS of 3 strings

Last Updated: 23 Feb, 2023

Hard

0/120

Avg time to solve 45 mins

Success Rate 50 %

9 upvotes

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:

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.

Auto

Console