What Is the Longest Common Subsequence?
The Longest Common Subsequence (LCS) finds the longest common subsequence of two sequences that preserves order but need not be contiguous. For example, the LCS of ABCBDAB and BDCAB is BCAB (length 4).
Unlike a substring, a subsequence doesn't have to be contiguous — you may skip gaps as long as the order holds. It powers file diffs and DNA comparison in bioinformatics.
Defining the State
dp[i][j] = the LCS length shared by the first i characters of A and the first j of B.
Adding one character at a time, you only need to ask "are the two end characters equal?".
The Recurrence
Compare A's i-th character with B's j-th:
- •Equal (A[i] == B[j]):
dp[i][j] = dp[i-1][j-1] + 1(add one common character) - •Different:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])(the longer side after dropping one character)
Equal → diagonal +1; different → max of up/left. That one line is the whole idea.
How It Works
Step 1. Set row 0 and column 0 to 0 (LCS with an empty string is 0).
Step 2. Fill the table from top-left to bottom-right; each cell follows the recurrence above.
Step 3. dp[m][n] is the length of the LCS.
Step 4 (recovery). If you need the actual sequence, trace back from dp[m][n]: on a match, move diagonally and record that character; otherwise move toward the larger neighbor.
The AlgoNote visualization fills the table and highlights the diagonal whenever characters match, step by step.
Time and Space Complexity
| Complexity | |
|---|---|
| Time | O(mn) |
| Space | O(mn) |
m, n are the two lengths. If only the length is needed, rolling two rows cuts space to O(n).
Walking Through an Example
Comparing A = ABCBDAB and B = BDCAB:
- •the longest order-preserving common pick is
BCAB(orBDAB) — length 4 - •the bottom-right cell of the table becomes 4
Note it need not be contiguous — B, C, A, B can be spread out as long as the order matches.
Common Mistakes
- •Confusing it with a substring: LCS doesn't require contiguity. If you need contiguity, that's the different "longest common substring" problem.
- •Index boundaries: omitting row/column 0 (empty string) misaligns
dp[i-1]references. - •Recovery direction: diagonal on match, larger neighbor otherwise — mixing it up recovers the wrong sequence.
See It in Action on AlgoNote
Watch the table fill as the two sequences' characters are compared and the length grows on a match, step by step on AlgoNote.