Longest Common Subsequence

What the longest common subsequence actually is

Given two sequences — say X = "ABCBDAB" and Y = "BDCAB" — a common subsequence is any sequence of symbols that you can obtain from both by deleting zero or more characters while keeping the survivors in their original left-to-right order. The longest common subsequence is the one of maximum length. For this pair, "BCAB" and "BDAB" are both length-4 LCSs — the length is unique (4), the sequence itself is not.

The key word is subsequence, not substring. A substring is contiguous; a subsequence may skip over characters. In "ABCBDAB", the string "ACD" is a valid subsequence (positions 1, 3, 5) but not a substring, because its characters are not adjacent in the original. That single distinction is what makes the problem interesting: there are up to 2ᵐ subsequences of a length-m string, so brute force — enumerating every subsequence of one string and testing it against the other — is exponential, roughly O(n · 2ᵐ). Dynamic programming reduces this to a quadratic O(mn) by exploiting overlapping subproblems.

Why LCS matters

• Version control and diff. Treat each line of a source file as a single symbol. The LCS of two file versions is the maximal set of unchanged lines that appear in the same order in both; everything else is an insertion or a deletion. This is exactly the output of diff, git diff, and three-way merge.
• Bioinformatics. DNA and protein sequence alignment is LCS's biological twin. The Needleman–Wunsch global-alignment algorithm (1970) is a weighted generalization of the LCS recurrence, scoring matches, mismatches, and gaps to align genomes and find conserved regions.
• Plagiarism and similarity detection. The ratio of LCS length to sequence length is a robust similarity metric that tolerates insertions and reordering better than exact substring matching.
• Spell-checking and fuzzy matching. Because LCS is tightly linked to insertion/deletion edit distance, it powers "did you mean…?" suggestions and record deduplication.

How the dynamic-programming solution works

Let dp[i][j] be the length of the LCS of the prefixes X[0..i) and Y[0..j). The recurrence is the whole algorithm:

• Empty prefix: dp[0][j] = dp[i][0] = 0 — an empty string shares nothing.
• Characters match (X[i-1] == Y[j-1]): dp[i][j] = dp[i-1][j-1] + 1. This matched symbol extends the best LCS of the shorter prefixes by one.
• Characters differ: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). At least one of the two current characters cannot be in the LCS, so drop it and take the better of the two smaller subproblems.

Fill the table row by row (or column by column). Each cell reads only its top, left, and top-left neighbors — all already computed — so every one of the (m+1)(n+1) cells costs O(1). The answer's length lands in the bottom-right cell dp[m][n]. Total time: O(mn). Naive space: O(mn) to hold the table.

Reconstructing the sequence: traceback

The table gives you the length; to recover the actual subsequence you walk backward from dp[m][n] to dp[0][0]. At each cell:

• If X[i-1] == Y[j-1], this character is part of the LCS — record it and step diagonally to dp[i-1][j-1].
• Otherwise move to whichever neighbor holds the larger value: up (dp[i-1][j]) or left (dp[i][j-1]). On a tie, either direction gives a valid — but possibly different — LCS.

You collect characters in reverse order, so reverse the buffer at the end. The traceback touches at most m + n cells, so it is O(m + n) once the table exists. The catch: reconstruction as described needs the whole O(mn) table in memory. Hirschberg's algorithm (1975) sidesteps this with divide-and-conquer — splitting X in half, using a linear-space forward and backward pass to find where the LCS crosses the split, and recursing — reconstructing the full sequence in O(mn) time but only O(m + n) space.

LCS vs. longest common substring vs. edit distance

	Longest Common Subsequence	Longest Common Substring	Edit (Levenshtein) Distance
Contiguous?	No — may skip characters	Yes — consecutive run	N/A (counts operations)
Recurrence on mismatch	max(up, left)	reset to 0	1 + min(up, left, diag)
Answer read from	Bottom-right cell	Global max over all cells	Bottom-right cell
Time	O(mn)	O(mn) DP, or O(m+n) with suffix automaton	O(mn)
Space (length only)	O(min(m, n))	O(min(m, n))	O(min(m, n))
Relationship	—	Different problem	Insert/delete-only distance = m + n − 2·LCS

The one-line difference between LCS and longest common substring — max(up, left) versus "reset to 0" — is a favorite interview trap. Skipping is allowed in one and forbidden in the other, and that changes both the recurrence and where you read the answer.

How it works in Python

def lcs_length(X, Y):
    m, n = len(X), len(Y)
    # dp[i][j] = LCS length of X[:i] and Y[:j]
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[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], dp


def lcs_reconstruct(X, Y):
    length, dp = lcs_length(X, Y)
    i, j = len(X), len(Y)
    out = []
    while i > 0 and j > 0:
        if X[i - 1] == Y[j - 1]:
            out.append(X[i - 1])      # part of the LCS
            i, j = i - 1, j - 1       # move diagonally
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1                     # move up
        else:
            j -= 1                     # move left
    return length, ''.join(reversed(out))


# lcs_reconstruct("ABCBDAB", "BDCAB") -> (4, "BCAB")   # >= tie-break; "BDAB" is an equally valid length-4 LCS

Two-row optimization for the length

Because dp[i][j] depends only on the current and previous rows, you can throw away everything older and keep just two rows — or even one row plus a saved diagonal. That drops space to O(min(m, n)) if you always iterate over the shorter string. This is enough when you only need the LCS length (or the edit distance derived from it). The moment you need the actual sequence, you either keep the full table or switch to Hirschberg's linear-space reconstruction.

def lcs_length_2row(X, Y):
    if len(X) < len(Y):           # iterate over the shorter Y for O(min(m,n)) space
        X, Y = Y, X
    prev = [0] * (len(Y) + 1)
    for i in range(1, len(X) + 1):
        cur = [0] * (len(Y) + 1)
        for j in range(1, len(Y) + 1):
            if X[i - 1] == Y[j - 1]:
                cur[j] = prev[j - 1] + 1
            else:
                cur[j] = max(prev[j], cur[j - 1])
        prev = cur
    return prev[len(Y)]

The sparse case: Hunt–Szymanski

The O(mn) table is wasteful when matches are rare — which is exactly the situation in line-based diff, where two files share only a handful of identical lines out of thousands. The Hunt–Szymanski algorithm (1977) exploits this. Instead of visiting every cell, it enumerates only the matchpoints — the pairs (i, j) where X[i] == Y[j] — and threads a longest increasing subsequence through them using a patience-sorting-style structure with binary search. If r is the number of matchpoints, it runs in O((r + n) log n). When matches are sparse (r ≈ n), that is nearly linear; when everything matches (r ≈ mn, e.g. two identical low-alphabet strings), it degrades back toward the quadratic bound. GNU diff and git instead use Myers' O(ND) algorithm (1986), a greedy diagonal search on the edit graph that costs O((m+n)·D) where D is the number of edits — extremely fast when files are similar.

Relation to edit distance

If the only edits allowed are insertions and deletions (no substitutions), the minimum number of edits to turn X into Y is m + n − 2·LCS(X, Y). The intuition: every character not in the LCS must be either deleted from X or inserted into Y. This is why LCS and the edit distance DP tables look almost identical — same shape, same O(mn) cost, a slightly different recurrence. Full Levenshtein distance also permits substitution, which breaks the clean identity but keeps the same tabular structure.

Common misconceptions and pitfalls

• Confusing subsequence with substring. The single most common error. LCS allows gaps; longest common substring does not. They need different recurrences.
• Assuming the LCS is unique. The length is unique; the sequence often is not. Traceback ties are genuine branch points.
• Optimizing to two rows, then trying to reconstruct. You cannot trace back through a table you threw away. Keep the full table, or use Hirschberg. Length-only optimization and reconstruction are mutually exclusive unless you use divide-and-conquer.
• Expecting a sub-quadratic general algorithm. Under the Strong Exponential Time Hypothesis, no O(n²⁻ᵉ) LCS algorithm exists (Abboud–Backurs–Williams, Bringmann–Künnemann, 2015). Speedups only come from special structure: sparse matches, small alphabet, or bit-parallelism (O(mn/w) where w is the word size).
• Off-by-one in the table. The table is (m+1)×(n+1) with a zero row and column for empty prefixes; index the strings as X[i-1] at table cell dp[i][j]. Mixing 0-indexed strings with 1-indexed table rows is the usual bug.