DPAlgorithmaka LCS

Longest Common Subsequence

Find the longest subsequence shared by two sequences using a 2D table over prefix pairs.

▶ Visualize Pattern: Dynamic Programming Practice (2)

Progress

Overview

Given strings a (length n) and b (length m), the LCS is the longest sequence that is a subsequence of both. For a = "abcde", b = "ace", the LCS is "ace" (length 3). It underlies diff, DNA alignment, and the "minimum insertions/deletions to transform" family; Edit Distance is its close cousin with substitutions.

The DP compares prefixes: dp[i][j] answers the question for a[:i] and b[:j]. When the last characters match they belong to the LCS; otherwise one of them is dropped and the better of the two options is kept.

2D DPtwo sequencessubsequenceO(n·m)rolling rows

Intuition

A mental model before the formal terms.

Compare "abcde" and "ace" from the end. e == e, so an optimal answer includes that e and reduces to LCS of "abcd" and "ac". Now d != c: either d is useless (try "abc" vs "ac") or c is useless (try "abcd" vs "a"). Taking the better of those and continuing gives "ac" + "e" = 3.

Lay out a grid with a along the rows and b along the columns. Each cell holds the LCS length of the two prefixes. A match lets you step diagonally up-left and add one; a mismatch lets you take the larger of the cell above and the cell to the left. The bottom-right cell is the answer and the diagonal steps on a walk back are the LCS characters.

How it works

State: dp[i][j] = LCS length of a[0..i) and b[0..j). Table size (n+1) × (m+1).
Transition: if a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Base case: dp[0][j] = dp[i][0] = 0 — an empty prefix shares nothing.
Iteration order: row-major, i from 1 to n, j from 1 to m; each cell needs its upper, left, and upper-left neighbors, all already computed.
Answer location: dp[n][m]. Reconstruct by walking from (n, m): on a match move diagonally and record the character; otherwise move toward the larger neighbor.
Space optimization: each row depends only on the previous row, so two rows of length m+1 suffice (O(min(n, m)) by putting the shorter string on the columns). Reconstruction, however, needs the full table or Hirschberg's divide-and-conquer trick.

Why it works

Optimal substructure: let Z be an LCS of a[0..i) and b[0..j). If a[i-1] == b[j-1], some LCS ends with that character (if Z does not, append it — it stays common and gets longer, contradiction — or swap its last char for it), so Z minus its last char is an LCS of the two shorter prefixes. If the last characters differ, Z cannot end with both, so it is an LCS of a[0..i-1),b[0..j) or of a[0..i),b[0..j-1). The transition covers precisely these cases.

The number of distinct (i, j) states is (n+1)(m+1) and each takes O(1), giving O(nm) — versus 2^n subsequences in brute force.

Correctness of the two-row optimization follows from the dependency structure: cell (i, j) never reads row i-2 or earlier.

Recognition

How to tell a problem wants this.

Two strings/sequences and a question about what they share, or the fewest edits limited to insert/delete to make them equal.
"Subsequence" (not substring) — order matters, contiguity does not.
Lengths up to a few thousand each — an n × m table of ~10⁷ cells fits.

“number of ways” → Dynamic Programming

Interactive visualization

Play, step, change the input. ← → and space work too.

String X | string Y — Two strings separated by a pipe — e.g. "ABCBDAB | BDCABA". Up to 10 characters each

	B	D	C	A	B	A
	0	0	0	0	0	0
A	·	·	·	·	·	·
B	·	·	·	·	·	·
C	·	·	·	·	·	·
B	·	·	·	·	·	·
D	·	·	·	·	·	·
A	·	·	·	·	·	·
B	·	·	·	·	·	·

1/44Row 0 and column 0 represent an empty prefix, whose LCS with anything is 0.

Cell being filledDependency readBase caseComputedReconstructed choice

PseudocodeLearn Longest Common Subsequence →

1dp[0][*] = dp[*][0] = 0
2for i in 1 .. m: for j in 1 .. n:
3  if X[i] == Y[j]: dp[i][j] = dp[i-1][j-1] + 1
4  else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
5traceback from dp[m][n]

Variables

Complexity

best O(n·m)

avg O(n·m)

worst O(n·m)

space O(min(n, m))

Speed

Pseudocode

1dp = (n+1) x (m+1) table of 0
2for i in 1..n:
3  for j in 1..m:
4    if a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1] + 1
5    else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
6return dp[n][m]

Implementations

1# dp[i][j] = LCS length of the prefixes a[0..i) and b[0..j).
2# Returns one actual LCS; its length is dp[n][m].
3def longest_common_subsequence(a: str, b: str) -> str:
4    n, m = len(a), len(b)
51 · State table
6    # Row 0 and column 0 stay 0: an empty prefix shares nothing.
7    dp = [[0] * (m + 1) for _ in range(n + 1)]
82 · Transition
9    for i in range(1, n + 1):
10        for j in range(1, m + 1):
11            if a[i - 1] == b[j - 1]:
12                dp[i][j] = dp[i - 1][j - 1] + 1
13            else:
14                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
153 · Answer
16    length = dp[n][m]  # LCS length lives in the last cell
174 · Reconstruction
18    chars: list[str] = []
19    i, j = n, m
20    while i > 0 and j > 0:
21        if a[i - 1] == b[j - 1]:
22            chars.append(a[i - 1])  # match: part of the LCS, move diagonally
23            i -= 1
24            j -= 1
25        elif dp[i - 1][j] >= dp[i][j - 1]:
26            i -= 1  # move toward the larger neighbor
27        else:
28            j -= 1
29    assert len(chars) == length
30    return "".join(reversed(chars))

Walkthrough

The table is a list-comprehension of fresh rows — [[0] * (m + 1) for _ in range(n + 1)]; the inner [0] * (m + 1) is safe because ints are immutable.
Prefix convention: dp[i][j] covers a[:i] and b[:j], so the characters compared are a[i - 1] and b[j - 1].
The walk-back appends matched characters in reverse order; "".join(reversed(chars)) restores left-to-right order in one pass.
The assert documents the invariant that reconstruction recovers exactly dp[n][m] characters.

Complexity (this implementation)

time O(n·m) · space O(n·m)

Length-only: two rows → O(min(n, m)) with the shorter string on columns. reversed() is a lazy iterator — no extra copy beyond the final join.

Language notes

Never write [[0] * (m + 1)] * (n + 1) — the outer * copies the ROW REFERENCE n + 1 times and every row aliases the same list.
Appending to a list then joining is the idiomatic O(n) string build; s = ch + s in a loop is quadratic.
For pure length on large inputs, difflib.SequenceMatcher solves related matching problems, but its ratio is not the LCS length — implement the table.

Common mistakes in this language

The [[0] * m] * n row-aliasing bug — writes show up in every row.
Using a[i]/b[j] instead of the - 1 offsets that the size-(n+1) table requires.
Recursing without memoization — 2^n blowup and the recursion limit long before that.

Language differences that matter here

2D-table construction is the trap outside C++: Python [[0]*m]*n and JS/TS fill(new Array(...)) both alias one row; C++ std::vector value-initialization builds independent rows by construction.
String building during reconstruction: C++ can write into a pre-sized std::string; JS/TS/Python strings are immutable — collect characters in an array/list and join once.
Cell values are small ints, so overflow is a non-issue in every language; memory is the binding constraint (C++ flat vectors and JS typed arrays shrink it, Python lists of ints are the heaviest).

Complexity

Best

O(n·m)

Average

O(n·m)

Worst

O(n·m)

Space

O(min(n, m))

Full table O(n·m) space is required for straightforward reconstruction; Hirschberg recovers the sequence in O(min(n, m)) space.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when

Similarity between two sequences where only insertions and deletions are allowed.
Diff tools, merge conflict detection, plagiarism and DNA similarity.
Derived problems: shortest common supersequence (n + m - LCS), minimum deletions to make strings equal, longest palindromic subsequence (LCS of s and reverse(s)).

Avoid it when

Longest common *substring* — needs the variant that resets to 0 on mismatch, or suffix automata for large inputs.
Both strings are 10^5+ long — O(nm) is too slow; use bit-parallel LCS or specialized algorithms (Hunt–Szymanski) when matches are sparse.
One sequence only (Longest Increasing Subsequence) — a different, 1D problem.

Alternatives

Edit Distance Longest Increasing Subsequence Subsequence DP Suffix Array

Common mistakes

Indexing off by one between dp[i] (prefix length i) and a[i-1] (the i-th character).
Adding 1 on a match but also taking the max with the non-diagonal neighbors — harmless for length but breaks reconstruction logic.
Attempting reconstruction from the two-row version, which has discarded the history.
Confusing subsequence with substring and resetting to 0 on mismatch.

Interview patterns

Longest Common Subsequence of two strings.
Longest Palindromic Subsequence via LCS with the reversed string.
Delete Operation for Two Strings: n + m - 2·LCS.
Uncrossed Lines / Max Dot Product of Two Subsequences — LCS-shaped tables.

Interview questions on this

Choosing between BFS, DFS, Dijkstra and DPAdvanced
When space complexity mattersIntermediate
Choosing a shortest-path algorithmAdvanced
Recognizing a dynamic-programming problemAdvanced

Mock interviews

Coin ChangeIntermediate

Example problems

Longest Common Subsequencemedium Edit Distancemedium

	B	D	C	A	B	A
	0	0	0	0	0	0
A	·	·	·	·	·	·
B	·	·	·	·	·	·
C	·	·	·	·	·	·
B	·	·	·	·	·	·
D	·	·	·	·	·	·
A	·	·	·	·	·	·
B	·	·	·	·	·	·

	B	D	C	A	B	A
	0	0	0	0	0	0
A	·	·	·	·	·	·
B	·	·	·	·	·	·
C	·	·	·	·	·	·
B	·	·	·	·	·	·
D	·	·	·	·	·	·
A	·	·	·	·	·	·
B	·	·	·	·	·	·

Overview

Intuition

How it works

Why it works

Recognition

Interactive visualization

Pseudocode

Implementations

Complexity

When to use — and when not to

Alternatives

Common mistakes

Interview patterns

Example problems

Related

	B	D	C	A	B	A
	0	0	0	0	0	0
A	·	·	·	·	·	·
B	·	·	·	·	·	·
C	·	·	·	·	·	·
B	·	·	·	·	·	·
D	·	·	·	·	·	·
A	·	·	·	·	·	·
B	·	·	·	·	·	·