Longest Common Subsequence (LCS) | Space optimized version

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++

Download   Run Code

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.
 

 

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++

Download   Run Code

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

Notify of
avatar
wpDiscuz