Write space optimized version of LCS problem.

We have discussed an iterative DP version of LCS problem here that uses O(mn) space where m and n are length of given strings X and Y respectively. If only the length of the LCS is required, the space complexity of the solution can be improved up to O(min(m, n)) as we’re reading only from previous row of current row.

### Approach 1: (Using two arrays)

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include <bits/stdc++.h> using namespace std; // Space optimized function to find length of Longest Common Subsequence // of substring X[0..m-1] and Y[0..n-1] int LCSLength(string X, string Y) { int m = X.length(), n = Y.length(); // allocate storage for one-dimensional arrays curr and prev int curr[n + 1], prev[n + 1]; // fill the lookup table in bottom-up manner for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0 || j == 0) curr[j] = 0; else { // if current character of X and Y matches if (X[i - 1] == Y[j - 1]) curr[j] = prev[j - 1] + 1; // else if current character of X and Y don't match else curr[j] = max(prev[j], curr[j - 1]); } } // replace contents of previous array with current array for (int i = 0; i <= n; i++) prev[i] = curr[i]; } // LCS will be last entry in the lookup table return curr[n]; } // Longest Common Subsequence problem space optimized solution int main() { string X = "XMJYAUZ", Y = "MZJAWXU"; cout << "The length of LCS is " << LCSLength(X, Y); return 0; } |

`Output:`

The length of LCS is 4

The time complexity of above solution is O(mn) and auxiliary space used by the program is 2n where n is the length of second string. The solution does not depend on the length of the first string. If length of second string is much larger than the length of first string, then the space complexity would be huge. We can optimize the space complexity to min(m, n) by creating a wrapper that always passes smaller string as second argument to the LCSLength function.

1 2 3 4 5 6 7 8 9 10 11 12 13 |
// main function int main() { string X = "XMJYAUZ", Y = "MZJAWXU"; // pass smaller string as second argument to LCSLength() if (X.length() > Y.length()) cout << "The length of LCS is " << LCSLength(X, Y); else cout << "The length of LCS is " << LCSLength(Y, X); return 0; } |

The auxiliary space used by the program now is 2 x min(m, n).

### Approach 2: (Using one array)

Above solution uses two arrays. Code can further be optimized to use only one array and a temporary variable.

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include <bits/stdc++.h> using namespace std; // Space optimized function to find length of Longest Common Subsequence // of substring X[0..m-1] and Y[0..n-1] int LCSLength(string X, string Y) { int m = X.length(), n = Y.length(); // allocate storage for one-dimensional array curr int curr[n + 1], prev; // fill the lookup table in bottom-up manner for (int i = 0; i <= m; i++) { prev = curr[0]; for (int j = 0; j <= n; j++) { int backup = curr[j]; if (i == 0 || j == 0) curr[j] = 0; else { // if current character of X and Y matches if (X[i - 1] == Y[j - 1]) curr[j] = prev + 1; // else if current character of X and Y don't match else curr[j] = max(curr[j], curr[j - 1]); } prev = backup; } } // LCS will be last entry in the lookup table return curr[n]; } // Longest Common Subsequence problem space optimized solution int main() { string X = "XMJYAUZ", Y = "MZJAWXU"; // pass smaller string as second argument to LCSLength() if (X.length() > Y.length()) cout << "The length of LCS is " << LCSLength(X, Y); else cout << "The length of LCS is " << LCSLength(Y, X); return 0; } |

`Output:`

The length of LCS is 4

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

excellent!!

Nice