LCS of 3 strings

Posted: 6 Nov, 2020
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

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
Approach 1

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