Longest Common Subsequence (LCS)¶
In one sentence
To compare two sequences, fill a grid where cell \((i, j)\) answers the question for the first \(i\) elements of one and the first \(j\) elements of the other. Each cell looks at only three neighbours.
1. What problem does it solve?¶
Example — AtCoder EDU DP F · LCS
Given strings \(s\) and \(t\) (each of length \(\le 3000\)), print one longest string that is a subsequence of both.
Input Output
axyb
abyxb axb (ayb is also accepted)
A subsequence keeps the order but may skip elements. axb is a subsequence of axyb (delete y) and of abyxb (delete the first b and the y).
A substring must be contiguous. LCS is about subsequences.
Brute force would try all \(2^{|s|}\) subsequences of \(s\). That is hopeless for length 3000.
2. The math¶
2.1 State¶
Row \(0\) and column \(0\) are empty prefixes, so they are \(0\). The answer is \(\mathrm{dp}_{n,m}\).
2.2 Transition¶
Look at the last elements \(a_i\) and \(b_j\).
Why the match case is safe. If \(a_i = b_j\), some longest common subsequence ends with this pair. Take any LCS. If it does not use \(a_i\) as its last element, its last element can be swapped for \(a_i\), and likewise for \(b_j\), without changing the length. So we match them and solve the rest: \(\mathrm{dp}_{i-1,j-1} + 1\).
Why the mismatch case is complete. If \(a_i \ne b_j\), they cannot both be the last element of a common subsequence. So at least one of them is unused. Drop \(a_i\) (giving \(\mathrm{dp}_{i-1,j}\)) or drop \(b_j\) (giving \(\mathrm{dp}_{i,j-1}\)), and take the better one.
b_j-1 b_j
a_i-1 [ i-1,j-1 ] [ i-1,j ]
a_i [ i, j-1 ] [ i, j ] <- reads only these three cells
So we fill rows top to bottom, and each row left to right.
2.3 Filling the table by hand¶
\(a =\) ACBDA (rows), \(b =\) ABCA (columns):
| \(\varnothing\) | A | B | C | A | |
|---|---|---|---|---|---|
| \(\varnothing\) | 0 | 0 | 0 | 0 | 0 |
| A | 0 | ↖1 | 1 | 1 | ↖1 |
| C | 0 | 1 | 1 | ↖2 | 2 |
| B | 0 | 1 | ↖2 | 2 | 2 |
| D | 0 | 1 | 2 | 2 | 2 |
| A | 0 | ↖1 | 2 | 2 | ↖3 |
↖ marks a match (\(a_i = b_j\)), where the value is diagonal \(+1\). Every other cell is the larger of the cell above and the cell to the left.
Recovering the string. Start at the bottom-right cell and walk back. At a match, record the letter and go ↖. Otherwise, move toward the larger of the cell above and the cell to the left, preferring up on ties. The bold cells are the matches on that path:
- Row A, column A (bottom-right) is a match: record
A, go ↖ to row D, column C. - D ≠ C, and above (2) ≥ left (2): go up to row B. B ≠ C, same tie: go up to row C.
- Row C, column C is a match: record
C, go ↖ to row A, column B. - A ≠ B, and above (0) < left (1): go left to row A, column A.
- Match: record
A.
Recorded back to front as A C A. Reversed, that is ACA, length \(3\).
2.4 Cost¶
The table has \((n + 1)(m + 1)\) cells, and each takes \(O(1)\). So time and memory are both \(O(nm)\). For \(3000 \times 3000\) that is \(9 \cdot 10^6\) cells.
3. Templates¶
These are the templates we use in class. Use them exactly as written.
What it is¶
A subsequence keeps elements in order but can skip some (e.g. ace is a subsequence of abcde). The LCS of two sequences is the longest subsequence present in both. Unlike a substring, the elements don't have to be contiguous.
Example: LCS of "AGGTAB" and "GXTXAYB" is "GTAB" (length 4).
The idea (dynamic programming)¶
Build a table dp where dp[i][j] = LCS length of the first i elements of a and the first j elements of b. Fill it with one rule:
- If the current two elements match, extend the diagonal:
dp[i-1][j-1] + 1. - If they don't, take the better of dropping one element from either side:
max(dp[i-1][j], dp[i][j-1]).
The extra row/column of zeros at index 0 is the base case (empty prefix → length 0), which is why the elements are indexed with -1.
Length only¶
def lcs_length(a, b):
n, m = len(a), len(b)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
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])
return dp[n][m]
print(lcs_length("abcde", "ace")) # 3
print(lcs_length([1, 3, 4, 1, 2], [3, 4, 2])) # 3
The same function works for strings or lists of ints — Python compares elements the same way either way.
Recovering the actual LCS¶
Fill the table as above, then walk backwards from dp[n][m], asking at each cell "how did this value get here?"
def lcs(a, b):
n, m = len(a), len(b)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
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])
# backtrack from bottom-right
i, j = n, m
result = []
while i > 0 and j > 0:
if a[i - 1] == b[j - 1]:
result.append(a[i - 1]) # part of the LCS
i -= 1
j -= 1
elif dp[i - 1][j] >= dp[i][j - 1]:
i -= 1 # move up
else:
j -= 1 # move left
result.reverse() # built back-to-front
return result
print("".join(lcs("AGGTAB", "GXTXAYB"))) # "GTAB"
print(lcs([1, 3, 4, 1, 2], [3, 4, 2])) # [3, 4, 2]
The backtrack rules mirror the fill rules: a match means the value came from the diagonal, so that element belongs to the LCS — record it and move up-left. No match means the value was inherited from a neighbor, so move toward the larger of dp[i-1][j] / dp[i][j-1]. Since elements are collected from the end, you reverse() at the finish. Return "".join(...) for a string, or the list directly for ints.
Key points¶
- Time & space: both
O(n·m). - If you only need the length, you can shrink to
O(m)space with two rolling rows — but then you can't backtrack, since reconstruction needs the full table. - When multiple LCS exist (ties), the
>=tie-break decides which one you get.
4. Worked solution — EDU DP F¶
The lcs template already returns the list of matched elements, so we read the two strings and join the result.
import sys
input = sys.stdin.readline
def lcs(a, b):
n, m = len(a), len(b)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
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])
# backtrack from bottom-right
i, j = n, m
result = []
while i > 0 and j > 0:
if a[i - 1] == b[j - 1]:
result.append(a[i - 1]) # part of the LCS
i -= 1
j -= 1
elif dp[i - 1][j] >= dp[i][j - 1]:
i -= 1 # move up
else:
j -= 1 # move left
result.reverse() # built back-to-front
return result
s = input().strip()
t = input().strip()
for ch in lcs(s, t):
print(ch, end="")
print()
Speed in Python
\(9 \cdot 10^6\) cells in nested Python loops is slow. Submit with PyPy.
5. The same grid, other problems¶
Once "prefix of \(a\) × prefix of \(b\)" feels natural, many problems are the same grid with a different rule per cell:
| problem | cell meaning | rule |
|---|---|---|
| LCS | longest common subsequence | match → ↖ \(+1\), else max(↑, ←) |
| edit distance | fewest edits to turn \(a_1..a_i\) into \(b_1..b_j\) | min(↑ \(+1\), ← \(+1\), ↖ \(+ [a_i \ne b_j]\)) |
| EDU DP H · Grid 1 | ways to reach cell \((i, j)\) | ↑ \(+\) ← mod \(10^9+7\) |
6. Common mistakes¶
Mixing string index and table index
Row \(i\) in the table is the element a[i - 1] in Python, because the table has an extra empty row. The template compares a[i - 1] == b[j - 1].
Forgetting .strip()
sys.stdin.readline() keeps the trailing "\n", which then becomes part of the "string" and can even match.
Substring vs. subsequence
Longest common substring needs dp = 0 on a mismatch, not max(↑, ←).
Rolling rows and then backtracking
Two rolling rows are enough for the length, but reconstruction needs the full table.
7. Practice¶
| Problem | Where | Idea |
|---|---|---|
| EDU DP F · LCS | AtCoder | this page |
| EDU DP H · Grid 1 | AtCoder | same grid order |
| LeetCode 1143 · Longest Common Subsequence | LeetCode | length only |
Credits & licenses
- Related grid problems (§5, §7): follow USACO Guide — Paths on Grids by Nathan Chen, Michael Cao, Benjamin Qi and Andrew Wang, licensed CC BY-NC-SA 4.0.
- Everything else (text, proofs, the worked table and backtrack) is ours. The templates in §3 are from our lessons.