Medium · Two-Sequence DP
Understand → Visualise → Practice.
Return the length of the longest sequence of characters appearing in order in both strings, not necessarily contiguously.
Let dp[i][j] be the LCS length of a's first i characters and b's first j. Matching last characters extend the diagonal; otherwise take the better of dropping one character.
dp[i][j] = LCS of a[:i] and b[:j]; row 0 and column 0 are 0.
If a[i−1] == b[j−1], dp[i][j] = dp[i−1][j−1] + 1; otherwise max(dp[i−1][j], dp[i][j−1]).
Each row only needs the previous one, so two rows of length |b| + 1 suffice; the answer is the last cell.
O(n × m) time and O(m) space.
A subsequence is not required to occupy adjacent positions.
Read the full guide first: Dynamic Programming.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.