LCS (Longest Common Subsequence) of three strings

19 June 2025

0

Given 3 strings of all having length < 100,the task is to find the longest common sub-sequence in all three given sequences.

Examples:

Input : str1 = "neveropen"  
        str2 = "neveropenfor"  
        str3 = "neveropen"
Output : 5
Longest common subsequence is "neveropen"
i.e., length = 5

Input : str1 = "abcd1e2"  
        str2 = "bc12ea"  
        str3 = "bd1ea"
Output : 3
Longest common subsequence is "b1e" 
i.e. length = 3.

This problem is simply an extension of LCS
Let the input sequences be X[0..m-1], Y[0..n-1] and Z[0..o-1] of lengths m, n and o respectively. And let L(X[0..m-1], Y[0..n-1], Z[0..o-1]) be the lengths of LCS of the three sequences X, Y and Z.

Following is the implementation:

The idea is to take a 3D array to store the 
length of common subsequence in all 3 given 
sequences i. e., L[m + 1][n + 1][o + 1]

1- If any of the string is empty then there
   is no common subsequence at all then
           L[i][j][k] = 0

2- If the characters of all sequences match
   (or X[i] == Y[j] ==Z[k]) then
        L[i][j][k] = 1 + L[i-1][j-1][k-1]

3- If the characters of both sequences do 
   not match (or X[i] != Y[j] || X[i] != Z[k] 
   || Y[j] !=Z[k]) then
        L[i][j][k] = max(L[i-1][j][k], 
                         L[i][j-1][k], 
                         L[i][j][k-1])

Below is implementation of above idea.

C++

// C++ program to find LCS of three strings
#include<bits/stdc++.h>
using namespace std;
 
/* Returns length of LCS for X[0..m-1], Y[0..n-1]
   and Z[0..o-1] */
int lcsOf3( string X, string Y, string Z, int m,
                               int n, int o)
{
    int L[m+1][n+1][o+1];
 
    /* Following steps build L[m+1][n+1][o+1] in
       bottom up fashion. Note that L[i][j][k]
       contains length of LCS of X[0..i-1] and
       Y[0..j-1]  and Z[0.....k-1]*/
    for (int i=0; i<=m; i++)
    {
        for (int j=0; j<=n; j++)
        {
            for (int k=0; k<=o; k++)
            {
                if (i == 0 || j == 0||k==0)
                    L[i][j][k] = 0;
 
                else if (X[i-1] == Y[j-1] && X[i-1]==Z[k-1])
                    L[i][j][k] = L[i-1][j-1][k-1] + 1;
 
                else
                    L[i][j][k] = max(max(L[i-1][j][k],
                                         L[i][j-1][k]),
                                     L[i][j][k-1]);
            }
        }
    }
 
    /* L[m][n][o] contains length of LCS for
      X[0..n-1] and Y[0..m-1] and Z[0..o-1]*/
    return L[m][n][o];
}
 
/* Driver program to test above function */
int main()
{
    string X = "AGGT12";
    string Y = "12TXAYB";
    string Z = "12XBA";
 
    int m = X.length();
    int n = Y.length();
    int o = Z.length();
 
    cout << "Length of LCS is " << lcsOf3(X, Y,
                                    Z, m, n, o);
 
    return 0;
}

Java

// Java program to find LCS of three strings
import java.io.*;
public class LCS_3Strings {
      
    /* Returns length of LCS for X[0..m-1], Y[0..n-1]
       and Z[0..o-1] */
    static int lcsOf3(String X, String Y, String Z, int m,
                                   int n, int o)
    {
        int[][][] L = new int[m+1][n+1][o+1];
      
        /* Following steps build L[m+1][n+1][o+1] in
           bottom up fashion. Note that L[i][j][k]
           contains length of LCS of X[0..i-1] and
           Y[0..j-1]  and Z[0.....k-1]*/
        for (int i=0; i<=m; i++)
        {
            for (int j=0; j<=n; j++)
            {
                for (int k=0; k<=o; k++)
                {
                    if (i == 0 || j == 0||k==0)
                        L[i][j][k] = 0;
      
                    else if (X.charAt(i - 1) == Y.charAt(j - 1) 
                                && X.charAt(i - 1)==Z.charAt(k - 1))
                        L[i][j][k] = L[i-1][j-1][k-1] + 1;
      
                    else
                        L[i][j][k] = Math.max(Math.max(L[i-1][j][k],
                                             L[i][j-1][k]),
                                         L[i][j][k-1]);
                }
            }
        }
      
        /* L[m][n][o] contains length of LCS for
          X[0..n-1] and Y[0..m-1] and Z[0..o-1]*/
        return L[m][n][o];
    }
      
    /* Driver program to test above function */
    public static void main(String args[])
    {
        String X = "AGGT12";
        String Y = "12TXAYB";
        String Z = "12XBA";
      
        int m = X.length();
        int n = Y.length();
        int o = Z.length();
      
        System.out.println("Length of LCS is " +
                                lcsOf3(X, Y,Z, m, n, o));
      
    }
}
// This code is contributed by Sumit Ghosh

Python3

# Python program to find
# LCS of three strings
 
# Returns length of LCS
# for X[0..m-1], Y[0..n-1]
# and Z[0..o-1]
def lcsOf3(X, Y, Z, m, n, o):
     
    L = [[[0 for i in range(o+1)] for j in range(n+1)]
         for k in range(m+1)]
 
    ''' Following steps build L[m+1][n+1][o+1] in
    bottom up fashion. Note that L[i][j][k]
    contains length of LCS of X[0..i-1] and
    Y[0..j-1] and Z[0.....k-1] '''
    for i in range(m+1):
        for j in range(n+1):
            for k in range(o+1):
                if (i == 0 or j == 0 or k == 0):
                    L[i][j][k] = 0
                     
                elif (X[i-1] == Y[j-1] and
                      X[i-1] == Z[k-1]):
                    L[i][j][k] = L[i-1][j-1][k-1] + 1
 
                else:
                    L[i][j][k] = max(max(L[i-1][j][k],
                    L[i][j-1][k]),
                                    L[i][j][k-1])
 
    # L[m][n][o] contains length of LCS for
    # X[0..n-1] and Y[0..m-1] and Z[0..o-1]
    return L[m][n][o]
 
# Driver program to test above function
 
X = 'AGGT12'
Y = '12TXAYB'
Z = '12XBA'
 
m = len(X)
n = len(Y)
o = len(Z)
 
print('Length of LCS is', lcsOf3(X, Y, Z, m, n, o))
 
# This code is contributed by Soumen Ghosh.                    

C#

// C# program to find 
// LCS of three strings
using System;
 
class GFG 
{
     
    /* Returns length of LCS 
    for X[0..m-1], Y[0..n-1]
    and Z[0..o-1] */
    static int lcsOf3(String X, String Y, 
                      String Z, int m,
                      int n, int o)
    {
        int [,,]L = new int[m + 1, 
                            n + 1, o + 1];
     
        /* Following steps build 
        L[m+1][n+1][o+1] in bottom 
        up fashion. Note that 
        L[i][j][k] contains length 
        of LCS of X[0..i-1] and
        Y[0..j-1] and Z[0.....k-1]*/
        for (int i = 0; i <= m; i++)
        {
            for (int j = 0; j <= n; j++)
            {
                for (int k = 0; k <= o; k++)
                {
                    if (i == 0 || 
                        j == 0 || k == 0)
                        L[i, j, k] = 0;
     
                    else if (X[i - 1] == Y[j - 1] && 
                             X[i - 1] == Z[k - 1])
                        L[i, j, k] = L[i - 1, 
                                       j - 1,
                                       k - 1] + 1;
     
                    else
                        L[i, j, k] = Math.Max(Math.Max(L[i - 1, j, k], 
                                                       L[i, j - 1, k]),
                                                       L[i, j, k - 1]);
                }
            }
        }
     
        /* L[m][n][o] contains length 
        of LCS for X[0..n-1] and
        Y[0..m-1] and Z[0..o-1]*/
        return L[m, n, o];
    }
     
    // Driver Code
    public static void Main()
    {
        string X = "AGGT12";
        string Y = "12TXAYB";
        string Z = "12XBA";
     
        int m = X.Length;
        int n = Y.Length;
        int o = Z.Length;
     
        Console.Write("Length of LCS is " + 
                       lcsOf3(X, Y, Z, m, n, o));
    }
}
 
// This code is contributed 
// by shiv_bhakt.

PHP

<?php 
// PHP program to find 
// LCS of three strings
 
/* Returns length of LCS for
X[0..m-1], Y[0..n-1] and Z[0..o-1] */
function lcsOf3($X, $Y, $Z, 
                $m, $n, $o)
{
    $L[$m + 1][$n + 1][$o + 1] = array(array(array()));
 
    /* Following steps build 
    L[m+1][n+1][o+1] in bottom 
    up fashion. Note that 
    L[i][j][k] contains length
    of LCS of X[0..i-1] and
    Y[0..j-1] and Z[0.....k-1]*/
    for ($i = 0; $i <= $m; $i++)
    {
        for ($j = 0; $j <= $n; $j++)
        {
            for ($k = 0; $k <= $o; $k++)
            {
                if ($i == 0 || $j == 0||$k == 0)
                    $L[$i][$j][$k] = 0;
 
                else if ($X[$i - 1] == $Y[$j - 1] && 
                         $X[$i - 1] == $Z[$k - 1])
                    $L[$i][$j][$k] = $L[$i - 1][$j - 1][$k - 1] + 1;
 
                else
                    $L[$i][$j][$k] = max(max($L[$i - 1][$j][$k],
                                              $L[$i][$j - 1][$k]),
                                             $L[$i][$j][$k - 1]);
            }
        }
    }
 
    /* L[m][n][o] contains length 
    of LCS for X[0..n-1] and 
    Y[0..m-1] and Z[0..o-1]*/
    return $L[$m][$n][$o];
}
 
// Driver code
$X = "AGGT12";
$Y = "12TXAYB";
$Z = "12XBA";
 
$m = strlen($X);
$n = strlen($Y);
$o = strlen($Z);
 
echo "Length of LCS is " . 
      lcsOf3($X, $Y, $Z, 
             $m, $n, $o);
 
// This code is contributed
// by ChitraNayal
?>

Javascript

<script>
// Javascript program to find LCS of three strings    
     
    /* Returns length of LCS for X[0..m-1], Y[0..n-1]
       and Z[0..o-1] */
    function lcsOf3(X,Y,Z,m,n,o)
    {
        let L = new Array(m + 1);
        for(let i = 0; i < m + 1; i++)
        {
            L[i] = new Array(n + 1);
            for(let j = 0; j < n + 1; j++)
            {
                L[i][j] = new Array(o + 1);
                for(let k = 0; k < o + 1; k++)
                {
                    L[i][j][k] = 0;
                }
            }
        }
         
        /* Following steps build L[m+1][n+1][o+1] in
           bottom up fashion. Note that L[i][j][k]
           contains length of LCS of X[0..i-1] and
           Y[0..j-1]  and Z[0.....k-1]*/
        for (let i = 0; i <= m; i++)
        {
            for (let j = 0; j <= n; j++)
            {
                for (let k = 0; k <= o; k++)
                {
                    if (i == 0 || j == 0 || k == 0)
                        L[i][j][k] = 0;
        
                    else if (X[i - 1] == Y[j - 1] 
                                && X[i - 1] == Z[k - 1])
                        L[i][j][k] = L[i - 1][j - 1][k - 1] + 1;
        
                    else
                        L[i][j][k] = Math.max(Math.max(L[i - 1][j][k],
                                             L[i][j - 1][k]),
                                         L[i][j][k - 1]);
                }
            }
        }
        
        /* L[m][n][o] contains length of LCS for
          X[0..n-1] and Y[0..m-1] and Z[0..o-1]*/
        return L[m][n][o];
    }
     
     /* Driver program to test above function */
     let X = "AGGT12";
     let Y = "12TXAYB";
     let Z = "12XBA";
     let m = X.length;
    let n = Y.length;
    let o = Z.length;
    
    document.write("Length of LCS is " +
                            lcsOf3(X, Y,Z, m, n, o));
     
    // This code is contributed by avanitrachhadiya2155
</script>

Output

Length of LCS is 2

Time Complexity: O(m*n*o))
Auxiliary Space: O(m*n*o)

Another approach: (Using recursion)

C++

// C++ program to find LCS of three strings
#include<bits/stdc++.h>
using namespace std;
 
    string X = "AGGT12"; 
    string Y = "12TXAYB"; 
    string Z = "12XBA"; 
 
int dp[100][100][100];
 
/* Returns length of LCS for X[0..m-1], Y[0..n-1]
and Z[0..o-1] */
int lcsOf3(int i, int j,int k)
{
    if(i==-1||j==-1||k==-1)
        return 0;
    if(dp[i][j][k]!=-1)
        return dp[i][j][k];
     
    if(X[i]==Y[j] && Y[j]==Z[k])
        return dp[i][j][k] = 1+lcsOf3(i-1,j-1,k-1);
    else
        return dp[i][j][k] = max(max(lcsOf3(i-1,j,k),
                            lcsOf3(i,j-1,k)),lcsOf3(i,j,k-1));
}
 
// Driver code
int main()
{
    memset(dp, -1,sizeof(dp));
    int m = X.length(); 
    int n = Y.length(); 
    int o = Z.length(); 
 
    cout << "Length of LCS is " << lcsOf3(m-1,n-1,o-1);
// this code is contributed by Kushdeep Mittal
}

Java

// Java program to find LCS of three strings
import java.io.*;
class GFG {
 
    static String X = "AGGT12";
    static String Y = "12TXAYB";
    static String Z = "12XBA";
 
    static int[][][] dp = new int[100][100][100];
 
    /* Returns length of LCS for X[0..m-1],
    Y[0..n-1] and Z[0..o-1] */
    static int lcsOf3(int i, int j, int k)
    {
        if (i == -1 || j == -1 || k == -1) {
            return 0;
        }
        if (dp[i][j][k] != -1) {
            return dp[i][j][k];
        }
 
        if (X.charAt(i) == Y.charAt(j)
            && Y.charAt(j) == Z.charAt(k)) {
            return dp[i][j][k]
                = 1 + lcsOf3(i - 1, j - 1, k - 1);
        }
        else {
            return dp[i][j][k]
                = Math.max(Math.max(lcsOf3(i - 1, j, k),
                                    lcsOf3(i, j - 1, k)),
                           lcsOf3(i, j, k - 1));
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 100; j++) {
                for (int k = 0; k < 100; k++) {
                    dp[i][j][k] = -1;
                }
            }
        }
        int m = X.length();
        int n = Y.length();
        int o = Z.length();
 
        System.out.print("Length of LCS is "
                         + lcsOf3(m - 1, n - 1, o - 1));
    }
}
 
// This code has been contributed by 29AjayKumar

Python3

# Python3 program to find LCS of
# three strings 
X = "AGGT12"
Y = "12TXAYB"
Z = "12XBA"
 
dp = [[[-1 for i in range(100)] 
           for j in range(100)] 
           for k in range(100)] 
         
# Returns length of LCS for 
# X[0..m-1], Y[0..n-1] and Z[0..o-1]
def lcsOf3(i, j, k) :
 
    if(i == -1 or j == -1 or k == -1) :
        return 0
         
    if(dp[i][j][k] != -1) :
        return dp[i][j][k]
     
    if(X[i] == Y[j] and Y[j] == Z[k]) :
        dp[i][j][k] = 1 + lcsOf3(i - 1, 
                                 j - 1, k - 1) 
        return dp[i][j][k]
         
    else :
        dp[i][j][k] = max(max(lcsOf3(i - 1, j, k), 
                              lcsOf3(i, j - 1, k)), 
                              lcsOf3(i, j, k - 1))
         
        return dp[i][j][k]
 
# Driver code 
if __name__ == "__main__" : 
    m = len(X)
    n = len(Y) 
    o = len(Z) 
 
    print("Length of LCS is", 
           lcsOf3(m - 1, n - 1, o - 1))
     
# This code is contributed by Ryuga

C#

// C# program to find LCS of three strings 
using System; 
 
class GFG 
{ 
static string X = "AGGT12"; 
static string Y = "12TXAYB"; 
static string Z = "12XBA"; 
 
static int[,,] dp = new int[100, 100, 100]; 
 
/* Returns length of LCS for X[0..m-1], 
Y[0..n-1] and Z[0..o-1] */
static int lcsOf3(int i, int j, int k) 
{ 
    if(i == -1 || j == -1 || k == -1) 
        return 0; 
    if(dp[i, j, k] != -1) 
        return dp[i, j, k]; 
     
    if(X[i] == Y[j] && Y[j] == Z[k]) 
        return dp[i, j, k] = 1 + lcsOf3(i - 1, j - 1, k - 1); 
    else
        return dp[i, j, k] = Math.Max(Math.Max(lcsOf3(i - 1, j, k), 
                                               lcsOf3(i, j - 1, k)),
                                               lcsOf3(i, j, k - 1)); 
} 
 
// Driver code 
static void Main() 
{ 
    for(int i = 0; i < 100; i++)
        for(int j = 0; j < 100; j++)
            for(int k = 0; k < 100; k++)
                dp[i, j, k] = -1;
    int m = X.Length; 
    int n = Y.Length; 
    int o = Z.Length; 
 
    Console.Write("Length of LCS is " + 
                   lcsOf3(m - 1, n - 1, o - 1)); 
}
}
 
// This code is contributed by DrRoot_

PHP

<?php
// PHP program to find LCS of three strings
 
    $X = "AGGT12"; 
    $Y = "12TXAYB"; 
    $Z = "12XBA"; 
 
    $dp=array_fill(0, 100, array_fill(0, 100, array_fill(0, 100, -1)));
 
/* Returns length of LCS for X[0..m-1], Y[0..n-1]
and Z[0..o-1] */
function lcsOf3($i, $j, $k)
{
    global $dp, $X, $Y, $Z;
    if($i == -1 || $j == -1 || $k == -1)
        return 0;
    if($dp[$i][$j][$k] != -1)
        return $dp[$i][$j][$k];
     
    if($X[$i] == $Y[$j] && $Y[$j] == $Z[$k])
        return $dp[$i][$j][$k] = 1+lcsOf3($i - 1, $j - 1, $k - 1);
    else
        return $dp[$i][$j][$k] = max(max(lcsOf3($i - 1, $j, $k),
                            lcsOf3($i, $j - 1, $k)), lcsOf3($i, $j, $k - 1));
}
 
// Driver code
    $m = strlen($X); 
    $n = strlen($Y); 
    $o = strlen($Z); 
 
    echo "Length of LCS is ".lcsOf3($m - 1, $n - 1, $o - 1);
 
// This code is contributed by mits
 
?>

Javascript

<script>
// Java program to find LCS of three strings
 
let X = "AGGT12";
let Y = "12TXAYB";
let Z = "12XBA";
 
let dp = new Array(100);
for(let i=0;i<100;i++)
{
    dp[i]=new Array(100);
    for(let j=0;j<100;j++)
    {
        dp[i][j]=new Array(100);
        for(let k=0;k<100;k++)
        {
            dp[i][j][k]=-1;
        }
    }
}
 
/* Returns length of LCS for X[0..m-1],
    Y[0..n-1] and Z[0..o-1] */
function lcsOf3(i,j,k)
{
     if (i == -1 || j == -1 || k == -1)
        {
            return 0;
        }
        if (dp[i][j][k] != -1)
        {
            return dp[i][j][k];
        }
  
        if (X[i] == Y[j] &&
            Y[j] == Z[k])
        {
            return dp[i][j][k] = 1 + lcsOf3(i - 1, j - 1, k - 1);
        } else {
            return dp[i][j][k] = Math.max(Math.max(lcsOf3(i - 1, j, k),
                                lcsOf3(i, j - 1, k)),
                                lcsOf3(i, j, k - 1));
        }
}
 
// Driver code
 
        let m = X.length;
        let n = Y.length;
        let o = Z.length;
  
        document.write("Length of LCS is "
                + lcsOf3(m - 1, n - 1, o - 1));
 
 
// This code is contributed by rag2127
</script>

Output

Length of LCS is 2

Time Complexity: O(m*n*o))
Auxiliary Space: O(m*n*o)

This article is contributed by Sahil Chhabra (akku). If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

LCS (Longest Common Subsequence) of three strings

C++

Java

Python3

C#

PHP

Javascript

C++

Java

Python3

C#

PHP

Javascript

Working with Titles and Heading – Python docx Module

Creating a Receipt Calculator using Python

One Liner for Python if-elif-else Statements

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US