Longest Common Subsequence (LCS) | Space optimized version
Write a space-optimized version of the LCS problem.
We have already discussed an iterative DP version of the LCS problem that uses O(m.n) space where m and n are the 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)) since we are only reading from the previous row of the current row.
Approach 1: (Using two arrays)
The space-optimized algorithm can be implemented as follows in C++, Java, and Python, 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 50 51 |
#include <iostream> #include <string> using namespace std; // Space optimized function to find the length of the 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 a 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 the current character of `X` and `Y` matches if (X[i - 1] == Y[j - 1]) { curr[j] = prev[j - 1] + 1; } // otherwise, if the current character of `X` and `Y` don't match else { curr[j] = max(prev[j], curr[j - 1]); } } } // replace contents of the previous array with the current array for (int i = 0; i <= n; i++) { prev[i] = curr[i]; } } // LCS will be the last entry in the lookup table return curr[n]; } int main() { string X = "XMJYAUZ", Y = "MZJAWXU"; cout << "The length of the LCS is " << LCSLength(X, Y); return 0; } |
Output:
The length of the LCS is 4
Java
|
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 |
class Main { // Space optimized function to find the length of the longest common subsequence // of substring `X[0…m-1]` and `Y[0…n-1]` public static int LCSLength(String X, String Y) { int m = X.length(), n = Y.length(); // allocate storage for one-dimensional arrays, `curr` and `prev` int[] curr = new int[n + 1]; int[] prev = new int[n + 1]; // fill the lookup table in a bottom-up manner for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i > 0 && j > 0) { // if the current character of `X` and `Y` matches if (X.charAt(i - 1) == Y.charAt(j - 1)) { curr[j] = prev[j - 1] + 1; } // otherwise, if the current character of `X` and `Y` don't match else { curr[j] = Integer.max(prev[j], curr[j - 1]); } } } // replace contents of the previous array with the current array System.arraycopy(curr, 0, prev, 0, n + 1); } // LCS will be the last entry in the lookup table return curr[n]; } public static void main(String[] args) { String X = "XMJYAUZ", Y = "MZJAWXU"; System.out.println("The length of the LCS is " + LCSLength(X, Y)); } } |
Output:
The length of the LCS is 4
Python
|
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 |
# Space optimized function to find the length of the longest common subsequence # of substring `X[0…m-1]` and `Y[0…n-1]` def LCSLength(X, Y): m = len(X) n = len(Y) # allocate storage for one-dimensional lists, `curr` and `prev` curr = [0] * (n + 1) prev = [0] * (n + 1) # fill the lookup table in a bottom-up manner for i in range(m + 1): for j in range(n + 1): if i > 0 and j > 0: # if the current character of `X` and `Y` matches if X[i - 1] == Y[j - 1]: curr[j] = prev[j - 1] + 1 # otherwise, if the current character of `X` and `Y` don't match else: curr[j] = max(prev[j], curr[j - 1]) # replace contents of the previous list with the current list prev = curr.copy() # LCS will be the last entry in the lookup table return curr[n] if __name__ == '__main__': X = 'XMJYAUZ' Y = 'MZJAWXU' print('The length of the LCS is', LCSLength(X, Y)) |
Output:
The length of the LCS is 4
The time complexity of the above solution is O(m.n), where m and n are the length of given strings X and Y, respectively. The auxiliary space required by the program is O(n), which is independent of the length of the first string m. However, if the second string’s length is much larger than the first string’s length, then the space complexity would be huge. We can optimize the space complexity to O(min(m, n)) by creating a wrapper that always passes a smaller string as a second argument to the LCSLength function.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
int main() { string X = "XMJYAUZ", Y = "MZJAWXU"; // pass smaller string as a second argument to `LCSLength()` if (X.length() > Y.length()) { cout << "The length of the LCS is " << LCSLength(X, Y); } else { cout << "The length of the LCS is " << LCSLength(Y, X); } return 0; } |
The program’s auxiliary space now is 2 x min(m, n).
Approach 2: (Using one array)
The above solution uses two arrays. We can further optimize the code to use only a single array and a temporary variable. The implementation can be seen below in C++, Java, and Python:
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 54 55 56 |
#include <iostream> #include <string> using namespace std; // Space optimized function to find the length of the 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 a 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 the current character of `X` and `Y` matches if (X[i - 1] == Y[j - 1]) { curr[j] = prev + 1; } // otherwise, if the current character of `X` and `Y` don't match else { curr[j] = max(curr[j], curr[j - 1]); } } prev = backup; } } // LCS will be the last entry in the lookup table return curr[n]; } int main() { string X = "XMJYAUZ", Y = "MZJAWXU"; // pass smaller string as a second argument to `LCSLength()` if (X.length() > Y.length()) { cout << "The length of the LCS is " << LCSLength(X, Y); } else { cout << "The length of the LCS is " << LCSLength(Y, X); } return 0; } |
Output:
The length of the LCS is 4
Java
|
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 |
class Main { // Space optimized function to find the length of the longest common subsequence // of substring `X[0…m-1]` and `Y[0…n-1]` public static int LCSLength(String X, String Y) { int m = X.length(), n = Y.length(); // allocate storage for one-dimensional array `curr` int[] curr = new int[n + 1]; int prev; // fill the lookup table in a 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 the current character of `X` and `Y` matches if (X.charAt(i - 1) == Y.charAt(j - 1)) { curr[j] = prev + 1; } // otherwise, if the current character of `X` and `Y` don't match else { curr[j] = Integer.max(curr[j], curr[j - 1]); } } prev = backup; } } // LCS will be the last entry in the lookup table return curr[n]; } public static void main(String[] args) { String X = "XMJYAUZ", Y = "MZJAWXU"; // pass smaller string as a second argument to `LCSLength()` if (X.length() > Y.length()) { System.out.println("The length of the LCS is " + LCSLength(X, Y)); } else { System.out.println("The length of the LCS is " + LCSLength(Y, X)); } } } |
Output:
The length of the LCS is 4
Python
|
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 |
# Space optimized function to find the length of the longest common subsequence # of substring `X[0…m-1]` and `Y[0…n-1]` def LCSLength(X, Y): m = len(X) n = len(Y) # allocate storage for one-dimensional list `curr` curr = [None] * (n + 1) # fill the lookup table in a bottom-up manner for i in range(m + 1): prev = curr[0] for j in range(n + 1): backup = curr[j] if i == 0 or j == 0: curr[j] = 0 else: # if the current character of `X` and `Y` matches if X[i - 1] == Y[j - 1]: curr[j] = prev + 1 # otherwise, if the current character of `X` and `Y` don't match else: curr[j] = max(curr[j], curr[j - 1]) prev = backup # LCS will be the last entry in the lookup table return curr[n] if __name__ == '__main__': X = 'XMJYAUZ' Y = 'MZJAWXU' # pass smaller string as a second argument to `LCSLength()` if len(X) > len(Y): print('The length of the LCS is', LCSLength(X, Y)) else: print('The length of the LCS is', LCSLength(Y, X)) |
Output:
The length of the LCS is 4
Also See:
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)