# LCS of 3 strings

Posted: 6 Nov, 2020
Difficulty: Hard

## PROBLEM STATEMENT

#### 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).)