If only the LCS LENGTH is needed (not the actual subsequence string), the DP table can be stored in
AO(min(m, n)) space using two rolling rows
BO(mn²) space because of duplicate paths
CO(1) space because length is just an integer
DO(m + n) space using a stack of indices
Answer & Solution
Correct answer: A. O(min(m, n)) space using two rolling rows
Each cell depends only on the row above and the cell to the left in the current row.
So keep two rolling rows
the older one can be discarded once it's been used to compute the newer.
O(min(m, n)) space if you orient rows along the shorter string.
You can't get O(1) because you do need the current and previous row
reconstructing the actual LCS does need the full table.
Keep practising Algorithms
Browse all Algorithms questions for GATE CSE, or explore more Computer Science topics.