Longest Common Subsequence
The problem
Find the length of the longest sequence obtainable from each of two strings by deleting characters without reordering those kept.
Example
"stone" and "longest" → 3, from "one"
Need a hint?
Compare the final characters of two prefixes.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
For matching characters, extend the diagonal prefix result by one. Otherwise take the maximum after dropping the last character from either prefix. Initialize the empty row and column to zero. Two rows suffice if you preserve the previous row while filling the current one.
Complexity
O(mn) time and O(n) space with two rows.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.