A Space Optimized Solution of LCS

Given two strings, find the length of longest subsequence present in both of them.

Examples:
LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.
LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4.

We have discussed typical dynamic programming based solution for LCS. We can optimize space used by lcs problem. We know recurrence relation of LCS problem is

 /* Returns length of LCS for X[0..m-1], Y[0..n-1] */ int lcs(string &X, string &Y) {     int m = X.length(), n = Y.length();     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]; }

How to find length of LCS in O(n) auxiliary space?

One important observation in above simple implementation is, in each iteration of outer loop we only, need values from all columns of previous row. So there is no need of storing all rows in our DP matrix, we can just store two rows at a time and use them, in that way used space will reduce from L[m+1][n+1] to L[n+1]. Below is the implementation of above idea.

div class="responsive-tabs">

C++

 // Space optimized C++ implementation // of LCS problem  #include using namespace std;    // Returns length of LCS  // for X[0..m-1], Y[0..n-1]  int lcs(string &X, string &Y) {            // Find lengths of two strings     int m = X.length(), n = Y.length();        int L[n + 1];        // Binary index, used to     // index current row and     // previous row.     bool bi;        for (int i = 0; i <= m; i++)     {                    // Compute current          // binary index         bi = i & 1;            for (int j = 0; j <= n; j++)         {             if (i == 0 || j == 0)                 L[bi][j] = 0;                else if (X[i-1] == Y[j-1])                  L[bi][j] = L[1 - bi][j - 1] + 1;                else                 L[bi][j] = max(L[1 - bi][j],                                 L[bi][j - 1]);         }     }        // Last filled entry contains     // length of LCS     // for X[0..n-1] and Y[0..m-1]      return L[bi][n]; }    // Driver code int main() {     string X = "AGGTAB";     string Y = "GXTXAYB";        printf("Length of LCS is %d ", lcs(X, Y));        return 0; }

Java

 // Java Code for A Space Optimized  // Solution of LCS    class GFG {            // Returns length of LCS      // for X[0..m - 1],     // Y[0..n - 1]      public static int lcs(String X,                            String Y)     {                    // Find lengths of two strings         int m = X.length(), n = Y.length();                int L[][] = new int[n+1];                // Binary index, used to index          // current row and previous row.         int bi=0;                for (int i = 0; i <= m; i++)         {                            // Compute current binary index             bi = i & 1;                    for (int j = 0; j <= n; j++)             {                 if (i == 0 || j == 0)                     L[bi][j] = 0;                        else if (X.charAt(i - 1) ==                           Y.charAt(j - 1))                     L[bi][j] = L[1 - bi][j - 1] + 1;                        else                     L[bi][j] = Math.max(L[1 - bi][j],                                          L[bi][j - 1]);             }         }                // Last filled entry contains length of          // LCS for X[0..n-1] and Y[0..m-1]          return L[bi][n];     }                   // Driver Code      public static void main(String[] args)      {         String X = "AGGTAB";         String Y = "GXTXAYB";                System.out.println("Length of LCS is " +                                     lcs(X, Y));     } }    // This code is contributed by Arnav Kr. Mandal.

Python3

 # Space optimized Python # implementation of LCS problem    # Returns length of LCS for  # X[0..m-1], Y[0..n-1] def lcs(X, Y):            # Find lengths of two strings     m = len(X)     n = len(Y)        L = [[0 for i in range(n+1)] for j in range(2)]        # Binary index, used to index current row and     # previous row.     bi = bool            for i in range(m):         # Compute current binary index         bi = i&1            for j in range(n+1):             if (i == 0 or j == 0):                 L[bi][j] = 0                elif (X[i] == Y[j - 1]):                 L[bi][j] = L[1 - bi][j - 1] + 1                else:                 L[bi][j] = max(L[1 - bi][j],                                 L[bi][j - 1])        # Last filled entry contains length of LCS     # for X[0..n-1] and Y[0..m-1]     return L[bi][n]    # Driver Code X = "AGGTAB" Y = "GXTXAYB"    print("Length of LCS is", lcs(X, Y))    # This code is contributed by Soumen Ghosh.

C#

 // C# Code for A Space  // Optimized Solution of LCS using System;    class GFG {            // Returns length of LCS      // for X[0..m - 1],     // Y[0..n - 1]      public static int lcs(string X,                           string Y)     {                    // Find lengths of         // two strings         int m = X.Length, n = Y.Length;                int [,]L = new int[2, n + 1];                // Binary index, used to          // index current row and          // previous row.         int bi = 0;                for (int i = 0; i <= m; i++)         {                            // Compute current             // binary index             bi = i & 1;                    for (int j = 0; j <= n; j++)             {                 if (i == 0 || j == 0)                     L[bi, j] = 0;                         else if (X[i - 1] == Y[j - 1])                     L[bi, j] = L[1 - bi,                                   j - 1] + 1;                        else                     L[bi, j] = Math.Max(L[1 - bi, j],                                          L[bi, j - 1]);             }         }                // Last filled entry contains         // length of LCS for X[0..n-1]         // and Y[0..m-1]          return L[bi, n];     }            // Driver Code      public static void Main()      {         string X = "AGGTAB";         string Y = "GXTXAYB";                Console.Write("Length of LCS is " +                                 lcs(X, Y));     } }    // This code is contributed  // by shiv_bhakt.

PHP



Output:

Length of LCS is 4

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