Question

Let X and Y be two arrays and you want to find their longest common sequence (LCS). Describe how you can calculate it in a space complexity of O(min{|X|, |Y|}). NOT O(|X| * |Y|). Pseudocode is not necessary but a detailed explanation of the idea will be very helpful.

Answer 1

Let the input sequences be X[0..m-1] and Y[0..n-1] of lengths m and n respectively. And let L(X[0..m-1], Y[0..n-1]) be the length of LCS of the two sequences X and Y. Following is the recursive definition of L(X[0..m-1], Y[0..n-1]).If last characters of both sequences match (or X[m-1] == Y[n-1]) then L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2])

If last characters of both sequences do not match (or X[m-1] != Y[n-1]) then

L(X[0..m-1], Y[0..n-1]) = MAX ( L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2]) ). So this problem has Overlapping Substructure property and recomputation of same subproblems can be avoided by either using Memoization or Tabulation.Time Complexity of the above implementation is O(mn).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[2][n+1].

This uses O(mn) space where m and n are length of given strings .If only the length of LCS is required,the sqpace complexity of the solution can be improved up to O(min(m,n)) as we are reading only from previous row of current row