Longest Common Subsequence (LCS) using Bottom-Up (Tabulation)

Longest Common Subsequence (LCS) using Memoization:

Longest Common Subsequence (LCS) using Bottom-Up (Space-Optimization):

We can use the following steps to implement the dynamic programming approach for LCS.

Create a 2D array dp[][] with rows and columns equal to the length of each input string plus 1 [the number of rows indicates the indices of S1 and the columns indicate the indices of S2].
Initialize the first row and column of the dp array to 0.
Iterate through the rows of the dp array, starting from 1 (say using iterator i).
- For each i, iterate all the columns from j = 1 to n:
  - If S1[i-1] is equal to S2[j-1], set the current element of the dp array to the value of the element to (dp[i-1][j-1] + 1).
  - Else, set the current element of the dp array to the maximum value of dp[i-1][j] and dp[i][j-1].
After the nested loops, the last element of the dp array will contain the length of the LCS.

See the below illustration for a better understanding:

Illustration:

Say the strings are S1 = “AGGTAB” and S2 = “GXTXAYB”.

First step: Initially create a 2D matrix (say dp[][]) of size 8 x 7 whose first row and first column are filled with 0.

Creating the dp table
Second step: Traverse for i = 1. When j becomes 5, S1[0] and S2[4] are equal. So the dp[][] is updated. For the other elements take the maximum of dp[i-1][j] and dp[i][j-1]. (In this case, if both values are equal, we have used arrows to the previous rows).

Filling the row no 1
Third step: While traversed for i = 2, S1[1] and S2[0] are the same (both are ‘G’). So the dp value in that cell is updated. Rest of the elements are updated as per the conditions.

Filling the row no. 2
Fourth step: For i = 3, S1[2] and S2[0] are again same. The updations are as follows.

Filling row no. 3
Fifth step: For i = 4, we can see that S1[3] and S2[2] are same. So dp[4][3] updated as dp[3][2] + 1 = 2.

Filling row 4
Sixth step: Here we can see that for i = 5 and j = 5 the values of S1[4] and S2[4] are same (i.e., both are ‘A’). So dp[5][5] is updated accordingly and becomes 3.

Filling row 5
Final step: For i = 6, see the last characters of both strings are same (they are ‘B’). Therefore the value of dp[6][7] becomes 4.

Filling the final row
So we get the maximum length of common subsequence as 4.

Following is a tabulated implementation for the LCS problem.

C++

// Dynamic Programming C++ implementation
// of LCS problem
#include <bits/stdc++.h>
using namespace std;

// Returns length of LCS for X[0..m-1],
// Y[0..n-1]
int lcs(string X, string Y, int m, int n)
{

    // Initializing a matrix of size
    // (m+1)*(n+1)
    int L[m + 1][n + 1];

    // Following steps build L[m+1][n+1]
    // in bottom up fashion. Note that
    // L[i][j] contains length of LCS of
    // X[0..i-1] and Y[0..j-1]
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                L[i][j] = 0;

            else if (X[i - 1] == Y[j - 1])
                L[i][j] = L[i - 1][j - 1] + 1;

            else
                L[i][j] = max(L[i - 1][j], L[i][j - 1]);
        }
    }

    // L[m][n] contains length of LCS
    // for X[0..n-1] and Y[0..m-1]
    return L[m][n];
}

// Driver code
int main()
{
    string S1 = "AGGTAB";
    string S2 = "GXTXAYB";
    int m = S1.size();
    int n = S2.size();

    // Function call
    cout << "Length of LCS is " << lcs(S1, S2, m, n);

    return 0;
}

Java

// Dynamic Programming Java implementation of LCS problem

import java.util.*;

public class LongestCommonSubsequence {

    // Returns length of LCS for X[0..m-1], Y[0..n-1]
    int lcs(String X, String Y, int m, int n)
    {
        int L[][] = new int[m + 1][n + 1];

        // Following steps build L[m+1][n+1] in bottom up
        // fashion. Note that L[i][j] contains length of LCS
        // of X[0..i-1] and Y[0..j-1]
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0)
                    L[i][j] = 0;
                else if (X.charAt(i - 1) == Y.charAt(j - 1))
                    L[i][j] = L[i - 1][j - 1] + 1;
                else
                    L[i][j] = max(L[i - 1][j], L[i][j - 1]);
            }
        }
        return L[m][n];
    }

    // Utility function to get max of 2 integers
    int max(int a, int b) { return (a > b) ? a : b; }

    public static void main(String[] args)
    {
        LongestCommonSubsequence lcs
            = new LongestCommonSubsequence();
        String S1 = "AGGTAB";
        String S2 = "GXTXAYB";
        int m = S1.length();
        int n = S2.length();

        System.out.println("Length of LCS is"
                           + " " + lcs.lcs(S1, S2, m, n));
    }
}

// This Code is Contributed by Saket Kumar

Python

# Dynamic Programming implementation of LCS problem


def lcs(X, Y, m, n):

    # Declaring the array for storing the dp values
    L = [[None]*(n+1) for i in range(m+1)]

    # Following steps build L[m+1][n+1] in bottom up fashion
    # Note: L[i][j] contains length of LCS of X[0..i-1]
    # and Y[0..j-1]
    for i in range(m+1):
        for j in range(n+1):
            if i == 0 or j == 0:
                L[i][j] = 0
            elif X[i-1] == Y[j-1]:
                L[i][j] = L[i-1][j-1]+1
            else:
                L[i][j] = max(L[i-1][j], L[i][j-1])

    # L[m][n] contains the length of LCS of X[0..n-1] & Y[0..m-1]
    return L[m][n]


# Driver code
if __name__ == '__main__':
    S1 = "AGGTAB"
    S2 = "GXTXAYB"
    m = len(S1)
    n = len(S2)
    print("Length of LCS is", lcs(S1, S2, m, n))

# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

// Dynamic Programming implementation of LCS problem
using System;

class GFG {
    // Returns length of LCS for X[0..m-1], Y[0..n-1]
    static int lcs(String X, String Y, int m, int n)
    {
        int[, ] L = new int[m + 1, n + 1];

        // Following steps build L[m+1][n+1]
        // in bottom up fashion.
        // Note that L[i][j] contains length of
        // LCS of X[0..i-1] and Y[0..j-1]
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0)
                    L[i, j] = 0;
                else if (X[i - 1] == Y[j - 1])
                    L[i, j] = L[i - 1, j - 1] + 1;
                else
                    L[i, j] = max(L[i - 1, j], L[i, j - 1]);
            }
        }
        return L[m, n];
    }

    // Utility function to get max of 2 integers
    static int max(int a, int b) { return (a > b) ? a : b; }

    // Driver code
    public static void Main()
    {
        String S1 = "AGGTAB";
        String S2 = "GXTXAYB";
        int m = S1.Length;
        int n = S2.Length;

        Console.Write("Length of LCS is"
                      + " " + lcs(S1, S2, m, n));
    }
}
// This Code is Contributed by Sam007

Javascript

// Dynamic Programming Java implementation of LCS problem

// Utility function to get max of 2 integers 
function max(a, b)
{
    if (a > b)
        return a;
    else
        return b;
}

// Returns length of LCS for X[0..m-1], Y[0..n-1] 
function lcs(X, Y, m, n)
{
    var L = new Array(m + 1);
    for(var i = 0; i < L.length; i++) 
    {
        L[i] = new Array(n + 1);
    }
    var i, j;
    
    /* Following steps build L[m+1][n+1] in
    bottom up fashion. Note that L[i][j]
    contains length of LCS of X[0..i-1]
    and Y[0..j-1] */
    for(i = 0; i <= m; i++)
    {
        for(j = 0; j <= n; j++)
        {
            if (i == 0 || j == 0)
                L[i][j] = 0;
            else if (X[i - 1] == Y[j - 1])
                L[i][j] = L[i - 1][j - 1] + 1;
            else
                L[i][j] = max(L[i - 1][j], L[i][j - 1]);
        }
    }
    
    /* L[m][n] contains length of LCS
    for X[0..n-1] and Y[0..m-1] */
    return L[m][n];
}

// Driver code
var S1 = "AGGTAB";
var S2 = "GXTXAYB";

var m = S1.length;
var n = S2.length;

console.log("Length of LCS is " + lcs(S1, S2, m, n));

// This code is contributed by akshitsaxenaa09

PHP

<?php 
// Dynamic Programming C# 
// implementation of LCS problem 
  
function lcs($X , $Y, $m, $n) 
{
    // Following steps build L[m+1][n+1] 
    // in bottom up fashion . 
    // Note: L[i][j] contains length of 
    // LCS of X[0..i-1] and Y[0..j-1]
    for ($i = 0; $i <= $m; $i++) 
    { 
        for ($j = 0; $j <= $n; $j++) 
        { 
            if ($i == 0 || $j == 0) 
                $L[$i][$j] = 0; 
            else if ($X[$i - 1] == $Y[$j - 1]) 
                $L[$i][$j] = $L[$i - 1][$j - 1] + 1; 
            else
                $L[$i][$j] = max($L[$i - 1][$j], 
                    $L[$i][$j - 1]); 
        } 
    } 
    // L[m][n] contains the length of 
    // LCS of X[0..n-1] & Y[0..m-1] 
    return $L[$m][$n]; 
} 

// Driver Code 
$S1 = "AGGTAB"; 
$S2 = "GXTXAYB";
$m = strlen($S1); 
$n = strlen($S2) ; 
echo "Length of LCS is "; 
echo lcs($S1, $S2, $m, $n); 

// This code is contributed 
// by Shivi_Aggarwal 
?>

Output

Length of LCS is 4

Time Complexity: O(m * n) which is much better than the worst-case time complexity of Naive Recursive implementation.
Auxiliary Space: O(m * n) because the algorithm uses an array of size (m+1)*(n+1) to store the length of the common substrings.