LCS (Longest Common Subsequence) of three strings

The problem “LCS (Longest Common Subsequence) of three strings” states that you are given 3 strings. Find out the longest common subsequence of these 3 strings. LCS is the string that is common among the 3 strings and is made of characters having the same order in all of the 3 given strings.

Example

"gxtxayb" 
"abgtab" 
"gyaytahjb"

Length of LCS: 4("gtab")

Approach

The problem gives us 3 strings as input and asked to find the longest common subsequence out of these. A subsequence is a string that is left when we delete some of the characters from the original string. Thus we need to find the common subsequence in the given 3 strings which has the maximum length.

The naive approach to the problem is quite similar to that of the normal Longest Common Subsequence problem. We had already discussed the LongestCommon Subsequence problem. But we also discussed that the naive approach is not efficient enough to solve the problem under the time limits. So, to solve the problem without exceeding the time limit. We will use dynamic programming for solving the question. The condition will be similar to that of LCS for 2 strings. Here we will have 3 states which will refer to indices in the 3 corresponding strings. So our dp array will be a 3D array, where we store 0 if any of the indices among the 3 of them is 0. If the character at all 3 indices is then we add 1 to the answer for the subproblem (LCS of substrings from length 0 to 1 less than each of the indices). If any of the two strings don’t have the same character then we store the maximum of the subproblems where decrement each of the index one by one.

Code

C++ code to find LCS of 3 strings

#include<bits/stdc++.h> 
using namespace std; 
  
int main() 
{ 
  string x = "gxtxayb"; 
  string y = "abgtab"; 
  string z = "gyaytahjb"; 
  int n = x.length(), m = y.length(), l = z.length();
  
  int dp[n][m][l];
  memset(dp, 0, sizeof dp);
  for (int i=0; i<n; i++){ 
    for (int j=0; j<m; j++){ 
      for (int k=0; k<l; k++){
        if (x[i] == y[j] && x[i] == z[k])
          dp[i][j][k] = ((i>0 && j>0 && k>0) ? dp[i-1][j-1][k-1] : 0) + 1;
        else
          dp[i][j][k] = max({i>0 ? dp[i-1][j][k] : 0, j>0 ? dp[i][j-1][k] : 0, k>0 ? dp[i][j][k-1] : 0}); 
      } 
    } 
  } 
  cout<<dp[n-1][m-1][l-1];
  return 0; 
}

4

Java code to find LCS of 3 strings

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    String x = "gxtxayb"; 
    String y = "abgtab"; 
    String z = "gyaytahjb"; 
    int n = x.length(), m = y.length(), l = z.length();
    
    int dp[][][] = new int[n][m][l];
    for (int i=0; i<n; i++){ 
      for (int j=0; j<m; j++){ 
        for (int k=0; k<l; k++){
          dp[i][j][k] = 0;
          if (x.charAt(i) == y.charAt(j) && x.charAt(i) == z.charAt(k))
            dp[i][j][k] = ((i>0 && j>0 && k>0) ? dp[i-1][j-1][k-1] : 0) + 1;
          else
            dp[i][j][k] = Math.max(Math.max(i>0 ? dp[i-1][j][k] : 0, j>0 ? dp[i][j-1][k] : 0), k>0 ? dp[i][j][k-1] : 0); 
        } 
      } 
    } 
    System.out.println(dp[n-1][m-1][l-1]);
  }
}

4

Complexity Analysis

Time Complexity

O(N*M*K), because we have to traverse all 3 strings having length N, M, and K. Because of using Dynamic Programming we are able to reduce the exponential time complexity to polynomial.

Space Complexity

O(N*M*K), because we have to create a 3D DP array for storing the result for smaller subproblem and then combining the result to obtain the answer for the initial problem. Thus finding the LCS (Longest Common Subsequence) of three strings has polynomial space complexity.