LCS of 3 Strings

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

We are solving this problem by solving its subproblems and then combining the solutions of those subproblems. If we analyze carefully, we will see that we are solving the same subproblems multiple times. Thus, this problem exhibits overlapping subproblems. Thus, in this approach, we will eliminate the need for solving the same subproblems again and again. 
 

Lets understand by an example:

Suppose we have 3 strings ‘virat’, ‘rohit’ and ‘rahul’. 

The below figure shows some of the recursive calls made for the given problem. 

As we can see, some subproblems are called multiple times. 

Same subproblems are shown in the same colour.

That’s why we are storing the solved subproblems in a lookup table so that we don’t have to solve them again. Whenever a call is made to the solved subproblem, we will directly return the answer of that subproblem stored in the lookup table.

Algorithm: 

1. The idea is to use memoization.
2. Create a 3D lookup table of size (N + 1) * (M + 1) * (K + 1) to store the solutions to the subproblems where lookUp[i][j][k] denotes the length of the longest common subsequence of string A[0..i], B[0..j], and C[0..k].
3. Initialize the table by -1.
4. Now, 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’.
5. The algorithm for the helper function will be as follows:
   
       int LCSHelper(A, B, C, N, M, K):

        1. If N or M or K becomes 0, return 0.

        2. Now, check if the current problem has already been solved or not. If it is already solved, return the value stored in the lookup table.

        3. That is, if lookup[N][M][K] is not equal to -1, return lookup[N][M][K].

        4. Initialize a variable ‘subAns’ by 0.

        5. Now, compare A[N - 1],  B[M - 1] and C[K - 1], 

              a. If they are equal, update ‘subAns’ as 1 + LCSHelper(A, B, C, N-1, M-1, K-1).

              b. If they are not equal, update ‘subAns’ as 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).

              c. Now, update the lookup[N][M][K] with ‘subAns’.

              d. Return lookup[N][M][K].

  6. Return answer.

Algorithm: 

• The idea is to create a 3-D DP of size (N + 1) * (M + 1) * (K + 1).
• Initially, all the elements of the DP table will be 0.
• Now, the value DP[i][j] denotes the length of the longest common subsequence of string A[0..i], B[0..j], and C[0..k].
• The detailed algorithm to fill the DP table will be as follows:
  1. Loop 1: For i = 1 to N:
  2. Loop 2: For j = 1 to M:
  3. Loop 3: For k = 1 to K:
     if(A[i] == B[j] == C[k] ), DP[i][j][k] += DP[i-1][j-1][k-1]

        else DP[i][j][k] = max(DP[i-1][j][k], DP[i][j-1][k], DP[i][j][k-1]) 

• Return DP[N][M][K].