Longest Common Subsequence
Find the longest subsequence shared by two strings without requiring contiguity.
Why does this pattern fit?
Restate the exact job
Find the longest subsequence shared by two strings without requiring contiguity.
Matching characters extend the diagonal answer; mismatches drop one side.
O(mn) time · O(min(m,n)) space
Using substring logic resets on mismatch and misses noncontiguous matches.
How to solve Longest Common Subsequence
The goal is to solve this problem from the pattern, not to memorize a finished answer. Use this as a check after your own attempt.
What the question asks
Find the longest subsequence shared by two strings without requiring contiguity.
Why Dynamic programming fits
Matching characters extend the diagonal answer; mismatches drop one side.
State to maintain
A DP grid or rolling row over suffix/prefix pairs.
Transition
On match use diagonal + 1; otherwise max of skipping either character.
Time and space
O(mn) time · O(min(m,n)) space
Counterexample to the tempting mistake
Using substring logic resets on mismatch and misses noncontiguous matches.
Prove it again tomorrow
Close this page. Rebuild the state and transition from memory, write a test that exposes the mistake above, then solve a fresh input without looking back. A same-day reread is practice, not proof of retention.