Practice free →
HomeGATE CSEcomputerscienceAlgorithms › If only the LCS LENGTH is needed (not the actual…

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.
Solve this in the app — GATE CSE practice & 24k+ MCQs →
Related questions