Longest Common Subsequence

Given two sequences A and B, the Longest Common Subsequence (LCS) is the longest sequence of characters that appears in both A and B in the same relative order, but not necessarily contiguously. For A = "ABCBDAB" and B = "BDCABA", one LCS is "BCBA" (length 4). LCS is the canonical 2D string DP and powers tools you use every day: Unix diff, Git’s merge resolution, spell-checkers, and DNA sequence alignment in bioinformatics. The standard solution by Wagner & Fischer (1974) runs in O(mn) time and O(mn) space; clever tricks (Hirschberg 1975) reduce space to O(min(m, n)) while preserving the ability to reconstruct the LCS itself.

1. Intuition — “Same Order, Skip Allowed”

The word “subsequence” is doing a lot of work, and confusing it with “substring” is the most common LCS misunderstanding.

A substring is a contiguous chunk: "BCB" is a substring of "ABCBDAB", but "BBA" is not (the characters are not contiguous).
A subsequence keeps the relative order but allows arbitrary deletions: "BBA" is a subsequence of "ABCBDAB" (take the B at index 1, the B at index 3, the A at index 5). You can drop any characters you like as long as the remaining ones appear in their original order.

Now imagine two friends each independently watch a movie series and write down their favorite scenes in the order they appeared. The LCS is the longest “shared narrative” both lists agree on — both friends mention these scenes, in the same order, possibly with extra scenes interleaved. That’s why LCS shows up in version control (git diff aligns shared lines, marks the rest as additions/deletions) and bioinformatics (aligning two DNA strands to spot conserved regions).

The decision-tree size for brute-force LCS is 2^min(m,n) — at each character of the shorter sequence you choose to include it or skip it. The DP collapses this exponential tree to O(mn) by recognizing that the answer for prefixes A[..i] and B[..j] depends only on (i, j), not on the path.

The first published O(mn) algorithm is Wagner & Fischer’s 1974 paper “The String-to-String Correction Problem” (JACM), which generalizes LCS to Edit Distance. The two problems are essentially the same DP machinery applied to slightly different recurrences — see §8 for the precise relationship.

2. Tiny Worked Example

Let A = "ABCBDAB" (length m = 7) and B = "BDCAB" (length n = 5).

State: dp[i][j] = length of the LCS of the prefixes A[0..i-1] and B[0..j-1]. So dp[0][*] = dp[*][0] = 0 (empty prefix has empty LCS).

Recurrence:

dp[i][j] = dp[i-1][j-1] + 1                     if A[i-1] == B[j-1]
        = max(dp[i-1][j], dp[i][j-1])           otherwise

Symbol-by-symbol unpacking:

A[i-1] and B[j-1] are the last characters of the prefixes (we use 1-indexed prefix lengths, 0-indexed string access).
If they match, the LCS of A[..i] and B[..j] is the LCS of A[..i-1] and B[..j-1] extended by that one character — hence +1.
If they don’t match, the LCS must drop the last character of one of the two prefixes. We try both: drop A[i-1] (giving dp[i-1][j]) or drop B[j-1] (giving dp[i][j-1]). Take the better.

We never need to consider dropping both characters simultaneously (i.e., dp[i-1][j-1]) because that case is dominated: dp[i-1][j-1] ≤ dp[i-1][j] and dp[i-1][j-1] ≤ dp[i][j-1] (LCS of larger prefixes can only grow or stay the same).

Build the table row by row. Columns indexed by B = "BDCAB", rows by A = "ABCBDAB":

After initialization (row 0 and column 0 all zero):

	B	D	C	A	B
ε	0	0	0	0	0
A
B
C
B
D
A
B

After filling row by row (computing each cell with the recurrence):

	B	D	C	A	B
ε	0	0	0	0	0
A	0	0	0	1	1
B	1	1	1	1	2
C	1	1	2	2	2
B	1	1	2	2	3
D	1	2	2	2	3
A	1	2	2	3	3
B	1	2	2	3	4

Answer: dp[7][5] = 4.

Let’s verify a few cells. dp[1][1]: A[0]='A', B[0]='B', mismatch → max(dp[0][1], dp[1][0]) = max(0, 0) = 0. ✓ dp[2][1]: A[1]='B', B[0]='B', match → dp[1][0] + 1 = 1. ✓ dp[2][5]: A[1]='B', B[4]='B', match → dp[1][4] + 1 = 1 + 1 = 2. ✓ dp[7][5]: A[6]='B', B[4]='B', match → dp[6][4] + 1 = 3 + 1 = 4. ✓

The reconstructed LCS (see §6) is "BCAB" — length 4. (Be careful: with this B = "BDCAB", the string "BCBA" is not a common subsequence — "BCBA" requires a second B after the A, which "BDCAB" does not have. "BCBA" is an LCS only for the longer B = "BDCABA" from the opening paragraph. The reconstruction code in §6, run on A="ABCBDAB", B="BDCAB", returns "BCAB".)

3. Pseudocode

lcs_length(A, B):
    m, n := length(A), length(B)
    dp := 2D array of size (m+1) × (n+1), all zeros
    for i := 1 to m:
        for j := 1 to n:
            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[m][n]

4. Python Implementation

4.1 Bottom-Up Tabulation, 2D

def lcs_length(A: str, B: str) -> int:
    m, n = len(A), len(B)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 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[m][n]

4.2 Bottom-Up Tabulation, 1D Rolling Array

Each row dp[i] depends only on dp[i-1], so we can keep two rows (or even one with a saved diagonal value):

def lcs_length_1d(A: str, B: str) -> int:
    if len(A) < len(B):
        A, B = B, A                                         # ensure B is shorter
    m, n = len(A), len(B)
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[j - 1]:
                curr[j] = prev[j - 1] + 1
            else:
                curr[j] = max(prev[j], curr[j - 1])
        prev, curr = curr, prev
        # reset curr (will be overwritten next iteration but be tidy)
    return prev[n]

This is O(min(m, n)) space. With more care (saving the diagonal value in a single scalar before overwriting prev[j-1]), you can reduce to a single O(n) array — but the two-row version is clearer and the space difference is constant-factor.

4.3 Top-Down Memoization

from functools import lru_cache
 
def lcs_memo(A: str, B: str) -> int:
    @lru_cache(maxsize=None)
    def helper(i: int, j: int) -> int:
        if i == 0 or j == 0:
            return 0
        if A[i - 1] == B[j - 1]:
            return helper(i - 1, j - 1) + 1
        return max(helper(i - 1, j), helper(i, j - 1))
    return helper(len(A), len(B))

The memoized version mirrors the recurrence almost word-for-word — useful when explaining the algorithm in interviews. See Memoization vs Tabulation for when to prefer this style.

5. Complexity

Time: O(mn). There are (m+1)(n+1) cells; each is filled in O(1) work (one comparison, one max over two values).

Space: O(mn) for the full 2D table; O(min(m, n)) for the rolling-array version; O(min(m, n)) for Hirschberg’s algorithm (§7) which also reconstructs the LCS in linear space.

Comparison-model lower bound. Be careful to state this correctly — it is widely mis-quoted. Aho, Hirschberg & Ullman proved (JACM 1976, “Bounds on the Complexity of the Longest Common Subsequence Problem”) that in the decision-tree model where every internal node is an equal/unequal comparison between two symbols, any LCS algorithm over an unbounded alphabet must perform Ω(mn) comparisons in the worst case — “unless a bound on the total number of distinct symbols is assumed, every solution to the problem can consume an amount of time that is proportional to the product of the lengths of the two strings” (Aho, Hirschberg & Ullman 1976). The bound is Ω(mn), not Ω(mn / log n) — there is no log factor in the AHU lower bound. This is the precise sense in which “no truly subquadratic comparison-based LCS exists in general.” The catch is the unbounded alphabet hypothesis: the moment the alphabet is fixed and finite, the bound no longer applies and faster algorithms become possible (see Masek-Paterson below). The AHU bound also does not constrain models richer than equal/unequal comparisons (e.g., RAM algorithms that index by symbol).

Subquadratic special cases. Two improvements escape O(mn) under extra assumptions. (1) The Hunt-Szymanski algorithm (CACM 1977) runs in O((r + n) log n) where r is the number of matching pairs (i, j) with A[i] = B[j]; when the alphabet is large and matches are sparse (typical of source-code line diffs) this is far below mn, though in the worst case r = mn and it degrades to O(mn log n). (2) For a constant-size alphabet, the Masek-Paterson algorithm (“A faster algorithm computing string edit distances,” JCSS 1980) applies the Four-Russians technique — precompute every possible t × t block of the DP table, choosing t ≈ log n, and look blocks up in O(1) — giving O(n² / log² n) for a constant alphabet and O(mn / log(min(m,n))) more generally. Note this is an upper bound (a faster algorithm), not a lower bound; the log factors here are a speed-up, the opposite of the AHU bound.

SETH-based conditional lower bound. For arbitrary alphabets no general subquadratic algorithm is known, and recent fine-grained complexity explains why: Abboud, Backurs & Williams (FOCS 2015, “Tight Hardness Results for LCS and Other Sequence Similarity Measures”) and, independently, Bringmann & Künnemann (FOCS 2015, “Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping”) proved that an O(n^{2-ε}) algorithm for LCS — for any ε > 0, even over a constant-size (indeed binary) alphabet — would refute the Strong Exponential Time Hypothesis (SETH), the conjecture that k-SAT has no O(2^{(1-ε)N}) algorithm (Abboud-Backurs-Williams 2015; Bringmann-Künnemann 2015). This generalized the analogous Edit Distance result of Backurs & Indyk (STOC 2015; arXiv:1412.0348). The SETH bound is n^{2-ε} — there are no log factors and it is not the n²/log²n upper bound above. For interview purposes, treat O(mn) as the answer and Ω(mn)/SETH-n^{2-ε} as the matching hardness story.

6. Reconstructing the LCS Itself

dp[m][n] gives the length, not the sequence. To recover the sequence, walk backward from (m, n):

def lcs_with_string(A: str, B: str) -> tuple[int, str]:
    m, n = len(A), len(B)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 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
    i, j = m, n
    out = []
    while i > 0 and j > 0:
        if A[i - 1] == B[j - 1]:
            out.append(A[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return dp[m][n], ''.join(reversed(out))
 
# lcs_with_string("ABCBDAB", "BDCAB") -> (4, 'BCAB')

The backtracking logic mirrors the forward recurrence: at each cell, we ask which of the three predecessors we came from. If the characters match, we must have come diagonally (and that character is in the LCS). Otherwise, we follow whichever neighbor (top or left) had the equal-or-larger value. Ties (multiple optimal LCSs exist) are broken arbitrarily — different tie-breaking rules give different LCS strings of the same length.

For all LCS strings (an exponentially large set in general), the backtracking generalizes to a recursion that explores both branches at every tie. Use sparingly; the count can be huge.

7. Hirschberg’s Linear-Space Algorithm

The 1D rolling array gives O(n) space but loses the ability to reconstruct. Hirschberg’s 1975 algorithm achieves both: O(min(m,n)) space and a reconstructed LCS, at the cost of a constant-factor slowdown.

The trick: divide-and-conquer. Cut A in half at row m/2. Run forward DP on A[..m/2] vs B and reverse DP on A[m/2..] vs B^R, both in O(n) space, capturing only the score arrays at the cut. Combine the two arrays to find the column j* such that dp_forward[j*] + dp_reverse[n - j*] is maximized — that’s the column at which the optimal LCS crosses the cut. Recurse on the two halves. Total time stays O(mn) (geometric series of halvings); total space is O(n).

A common myth — repeated in some tutorials — is that Hirschberg’s algorithm “is what git diff uses.” That is wrong. Git’s default line-level diff is the Myers greedy/divide-and-conquer algorithm (Myers 1986), implemented in xdiff/xdiffi.c in Git’s bundled, modified copy of libxdiff: “Since libxdiff used Eugene W. Myers’s algorithm, the diff strategy was called myers. To this day it is still the default way git perform all diffs on text” (Sanglard, Git diff code review). Git additionally offers minimal, patience (xdiff/xpatience.c), and histogram (xdiff/xhistogram.c) via diff.algorithm, none of which are Hirschberg (git diff-options docs). Myers’ own algorithm uses a linear-space refinement that is itself a Hirschberg-style divide-and-conquer on the edit graph, so the technique survives in Git — but the headline “Git uses Hirschberg’s LCS algorithm” conflates the two and is inaccurate. Where Hirschberg’s space-reduction idea genuinely matters is in bioinformatics alignment (aligning genome-scale sequences in O(n) rather than O(n²) space).

8. Relationship to Edit Distance, Diff, and Levenshtein

LCS and Edit Distance are duals.

Edit Distance (Levenshtein 1965): minimum number of insertions, deletions, and substitutions to transform A into B.
LCS-based distance: minimum number of insertions and deletions to transform A into B (no substitutions allowed). This equals m + n − 2 · LCS(A, B) — every character not in the LCS must be either deleted (if in A) or inserted (if in B).

So if you know LCS, you immediately know one variant of edit distance. Levenshtein (which allows substitution) requires a different recurrence (three options instead of two — see Edit Distance) but the DP table shape is identical: (m+1) × (n+1).

Diff algorithms (Unix diff, Git): the “shared lines” between two files form an LCS (treating each line as a single character in a giant alphabet). The non-LCS lines are the ”+” and ”−” markers in the diff output. The Myers (1986) algorithm, used in many diff implementations, computes the LCS in O((m+n)D) where D is the size of the difference — much faster when files are similar.

Bioinformatics: the Needleman-Wunsch algorithm (1970) for global DNA sequence alignment is essentially LCS with weighted scoring (match bonus, mismatch penalty, gap penalty). Smith-Waterman (1981) does local alignment: find the best-scoring substring alignment, used to find conserved domains.

9. Variants Worth Knowing

9.1 Longest Common Substring (Contiguous)

Different problem, similar DP. dp[i][j] = length of LCS of A[..i] and B[..j] ending exactly at i and j. Recurrence: dp[i][j] = dp[i-1][j-1] + 1 if A[i-1] == B[j-1], else 0. The answer is max over the whole table, not dp[m][n]. Same O(mn) complexity. Don’t confuse with LCS — substring requires contiguity, subsequence does not.

9.2 Shortest Common Supersequence

Find the shortest sequence containing both A and B as subsequences. The length is m + n − LCS(A, B); reconstruction overlays the two strings using the LCS as the shared backbone.

9.3 LCS of Three or More Sequences

Extends to O(n_1 · n_2 · n_3) with a 3D table for three sequences. NP-hard in the general case (number of sequences in the input is part of the input).

9.4 Approximate / Bounded-Difference Variant

When the answer is known to be close to min(m, n) (i.e., the strings are very similar), the Ukkonen-style “diagonal” optimization restricts the DP to a band of width O(D) around the diagonal, achieving O((m+n)D) where D is the difference. Very common in spell-check / typo-correction.

9.5 LCS as Longest Increasing Subsequence

A famous trick: if B is a permutation of A (or both come from the same character set with no duplicates), LCS reduces to Longest Increasing Subsequence in O(n log n). Map each character of B to its position in A, then find LIS in the resulting sequence. Used in some specialized scoring problems.

10. Common Interview Problems

Problem	LeetCode #	Pattern
Longest Common Subsequence	LC 1143	The base problem
Edit Distance	LC 72	Same DP shape, different recurrence
Longest Palindromic Subsequence	LC 516	LCS of S and reverse(S)
Delete Operation for Two Strings	LC 583	min deletions = m + n − 2·LCS
Shortest Common Supersequence	LC 1092	Build using LCS backbone
Distinct Subsequences	LC 115	Count, not max-length
Longest Common Substring	(variant)	Contiguous version, different recurrence

11. Diagram — The 2D DP Table Filling

flowchart LR
  TL[dp i-1, j-1] -- match: +1 --> C[dp i, j]
  T[dp i-1, j] -- mismatch: max --> C
  L[dp i, j-1] -- mismatch: max --> C

What this diagram shows. Computing one cell dp[i][j] reads at most three predecessors: the diagonal dp[i-1][j-1] (used only when characters match — we extend the previous LCS by 1), the cell above dp[i-1][j] (one option in the mismatch case — drop A[i-1]), and the cell to the left dp[i][j-1] (the other mismatch option — drop B[j-1]). Two of the three are always in the row above, which is what makes the rolling-array O(min(m,n)) space optimization possible: keep only the previous row and one scalar holding the diagonal value before it gets overwritten. The arrows in this diagram are also exactly the back-pointers used during reconstruction (§6) — at each cell during backtracking, we follow the arrow we came in on.

12. Pitfalls

12.1 Confusing Subsequence with Substring

The single most common LCS mistake. A “substring” must be contiguous; a “subsequence” need not be. Different DPs entirely. Read the problem twice and pin down which it means before coding.

12.2 Off-by-One in Indexing

The cleanest convention: dp has dimensions (m+1) × (n+1), with dp[0][*] and dp[*][0] as the base case (empty-prefix LCS = 0). Then dp[i][j] refers to the LCS of the first i characters of A and the first j characters of B, accessed in code as A[i-1] and B[j-1] (0-indexed). Mixing 0-indexed states with 0-indexed strings is a frequent source of bugs.

12.3 Wrong Base Case

dp[0][j] = 0 and dp[i][0] = 0. Easy to get from zero-initialization, but if you initialize the table differently (e.g., for edit distance you want dp[0][j] = j), don’t blindly copy.

12.4 Forgetting to Reset Rolling Array

In the 1D rolling-array version, after swapping prev and curr, the new curr still holds the previous-iteration values. If you assume zero-init, you’ll get wrong answers. Either zero-fill curr at the top of each iteration or explicitly write every cell.

12.5 In-Place Update in 1D Optimization

Unlike 01 Knapsack, LCS’s 1D optimization with a single array requires careful handling because both dp[j-1] (just-updated, current-row) and dp[j-1] (need previous-row diagonal value) are needed in the same step. The two-row version (§4.2) avoids this; if you compress further to one row, save the diagonal in a scalar before overwriting.

12.6 Trying to Reconstruct From Rolling Array

Throwing away intermediate rows means losing the back-pointer information needed to reconstruct the actual LCS string. Either keep the full table, store taken[i][j] direction markers separately, or use Hirschberg’s divide-and-conquer (§7).

12.7 Recursive Memoization Stack Depth

For long strings (m + n > 10^4), Python’s recursion limit kicks in. Either sys.setrecursionlimit(10**6) and increase OS stack, or use iterative tabulation. See the corresponding pitfall in Memoization vs Tabulation.

12.8 Multiple Optimal LCSs

The reconstruction returns one LCS, not all of them. If the problem asks for “the lexicographically smallest LCS” or “all LCSs,” the backtracking must be modified — for “smallest,” prefer the diagonal/up moves in a canonical order; for “all,” explore both ties at every branch (potentially exponential).

12.9 Treating LCS as Symmetric

LCS is symmetric (LCS(A, B) = LCS(B, A) as a length), but the reconstructed string may differ depending on which is the “row” axis vs “column” axis under tie-breaking. Pick one convention.

13. Open Questions

When does Hunt-Szymanski beat the textbook DP in practice? When the alphabet is large and the number of matching pairs r is small — typical for source-code diffs where most lines are unique.
Is there a practical truly subquadratic LCS algorithm for general alphabets? No — Abboud-Backurs-Williams 2015 and Bringmann-Künnemann 2015 independently proved an O(n^{2-ε}) LCS algorithm would refute SETH (Backurs-Indyk 2015 proved the analogous edit-distance result). The constant-alphabet Four-Russians O(n²/log²n) speed-up is a log-factor win only, not a polynomial improvement, and is rarely worth the bookkeeping in practice.
Why does Git’s diff sometimes prefer “patience diff” or “histogram diff” over LCS-based diff? Because they produce more human-readable hunks, especially when refactored code creates near-duplicate lines that confuse LCS-based alignment. Quality, not speed.

14. See Also

Edit Distance — closely related 2D string DP with three operations
Longest Increasing Subsequence — different sequence DP; LCS reduces to LIS in special cases
Memoization vs Tabulation — the foundational DP framework
01 Knapsack — another canonical 2D DP
Big-O Notation — pseudo-quadratic complexity discussion
SWE Interview Preparation MOC

vault

Explorer

Longest Common Subsequence

Longest Common Subsequence

1. Intuition — “Same Order, Skip Allowed”

2. Tiny Worked Example

3. Pseudocode

4. Python Implementation

4.1 Bottom-Up Tabulation, 2D

4.2 Bottom-Up Tabulation, 1D Rolling Array

4.3 Top-Down Memoization

5. Complexity

6. Reconstructing the LCS Itself

7. Hirschberg’s Linear-Space Algorithm

8. Relationship to Edit Distance, Diff, and Levenshtein

9. Variants Worth Knowing

9.1 Longest Common Substring (Contiguous)

9.2 Shortest Common Supersequence

9.3 LCS of Three or More Sequences

9.4 Approximate / Bounded-Difference Variant

9.5 LCS as Longest Increasing Subsequence

10. Common Interview Problems

11. Diagram — The 2D DP Table Filling

12. Pitfalls

12.1 Confusing Subsequence with Substring

12.2 Off-by-One in Indexing

12.3 Wrong Base Case

12.4 Forgetting to Reset Rolling Array

12.5 In-Place Update in 1D Optimization

12.6 Trying to Reconstruct From Rolling Array

12.7 Recursive Memoization Stack Depth

12.8 Multiple Optimal LCSs

12.9 Treating LCS as Symmetric

13. Open Questions

14. See Also

Graph View

Table of Contents

Backlinks