Longest Common Subsequence in Python: How diff Tools Work

TRACE and CRATE are built from exactly the same five letters. But the longest run of letters you can read off both of them in order is only three long: RAE. That gap between "same letters" and "same order" is the entire subject of this post.

The longest common subsequence — LCS — of two sequences is the longest list of elements that appears in both, in the same relative order, with gaps allowed. It is the classic dynamic programming exercise, and unlike most interview DP you meet it daily without noticing: every git diff you read answers almost exactly this question, with whole lines of a file playing the part of letters.

What follows defines subsequence precisely — confusing it with substring is how most people get this wrong — derives the recurrence, fills a table by hand, backtracks through it to recover the subsequence itself rather than just its length, and ends with a working line diff.

The idea

A subsequence is what you get by deleting zero or more elements and keeping the rest in order. A substring is stricter: the kept elements must also be adjacent. So in ABCDEF, ACF is a subsequence but not a substring, CDE is both, and FAC is neither — the letters are all there, but not in that order.

Python has an operator for one and not the other, which is worth noticing: "RAC" in "TRACE" tests for a substring. Testing for a subsequence takes a loop.

def is_subsequence(candidate: str, text: str) -> bool:
    """True when candidate can be read off text by deleting characters only."""
    position = 0
    for character in text:
        if position < len(candidate) and character == candidate[position]:
            position += 1
    return position == len(candidate)


print(is_subsequence("RAE", "TRACE"), is_subsequence("RAE", "CRATE"))
print("RAE" in "TRACE", "RAC" in "TRACE")

True True
False True

RAE sits inside both words as a subsequence and inside neither as a substring. That is the answer we want the algorithm to find.

The recurrence

Look only at the last element of each sequence. There are two cases, and both shrink the problem.

They match. Say both end in E. Then some longest common subsequence ends with that E, so pair them up, count 1, and solve the same problem with both last elements removed:

LCS(a, b) = 1 + LCS(a without its last, b without its last)

They differ. No common subsequence can use both as its final element, so at least one of the two is useless. You do not know which, so try both and keep the better answer:

LCS(a, b) = max(LCS(a without its last, b), LCS(a, b without its last))

The base case is an empty sequence, which shares nothing with anything: 0.

That is already a complete algorithm, and running it literally is catastrophically slow: the two branches of the mismatch case overlap enormously, asking each other the same questions over and over. Dynamic programming fixes that by giving every distinct question a cell in a table and answering each one once.

The questions have a tidy shape. Every call is about a prefix of a and a prefix of b, and a prefix is just a length. So the problem space is a grid of (len(a) + 1) × (len(b) + 1) cells, where cell [i][j] holds the LCS length of the first i elements of a and the first j of b.

Watching it work

Put a = "TRACE" down the side and b = "CRATE" across the top. Row 0 and column 0 mean "the empty prefix", so they start at zero.

Read the recurrence as a rule about neighbours. Cell [i][j] compares the i-th letter of TRACE with the j-th letter of CRATE:

• They match — take the cell diagonally up-left and add 1.
• They differ — take the larger of the cell above and the cell to the left.

Both of those are already filled if you sweep left to right, top to bottom. Here is every row.

Row T — T against C, R, A finds nothing, and the cells above and left are all 0. Against T in column 4: match, so 1 + the diagonal 0 = 1. Against E: max(above 0, left 1) = 1. The row is 0 0 0 0 1 1.

Row R — against R: match, 1 + diagonal 0 = 1. Every other column mismatches and inherits a 1. The row is 0 0 1 1 1 1. Look at where TR meets CRAT: both hold a T and an R, but TR has the T first and CRAT has it last, so only one of the two letters is ever usable. The answer is 1, not 2 — the whole difficulty of the problem in one cell.

Row A — against A: match, 1 + the diagonal (the TR/CR cell, holding 1) = 2. The last two columns inherit that 2. The row is 0 0 1 2 2 2.

Row C — against C: match, but the diagonal is a row-0 cell, so 1 + 0 = 1. The C matched and earned almost nothing, being the first letter of CRATE and the fourth of TRACE. The rest takes maxima: 0 1 1 2 2 2.

Row E — the first four columns give 1, 1, 2, 2. Against E: match, so 1 + the diagonal, the TRAC/CRAT cell holding 2, giving 3. The row is 0 1 1 2 2 3.

The bottom-right cell, 3, is the length of the longest common subsequence of the two full words.

Backtracking to the actual answer

The table only holds numbers. To get RAE out of it, walk backwards from the bottom-right corner asking, at each cell, which rule produced this number? If the two letters match, it came from the diagonal: record the letter and step diagonally. Otherwise step to whichever of the cells above and left holds the larger value; on a tie, either works.

Starting at [5][5]:

1. E and E match — record E, move to [4][4].
2. C against T: above holds 2, left holds 2 — a tie, so step up to [3][4].
3. A against T: above holds 1, left holds 2, so step left to [3][3].
4. A and A match — record A, move to [2][2].
5. R and R match — record R, move to [1][1].
6. T against C: both neighbours hold 0, so step up into row 0 and stop.

Recorded in that order: E, A, R. Reverse them and you have RAE.

Step 2 matters: the tie means there is more than one correct answer of length 3. Break it the other way and you get a different but equally long subsequence. LCS is a longest, not the longest.

The code

Start with the recurrence written out literally, with a counter bolted on so the cost is visible.

NAIVE_CALLS = 0


def lcs_length_naive(a: str, b: str) -> int:
    """LCS length by trying every choice at every step. Correct, and unusable."""
    global NAIVE_CALLS
    NAIVE_CALLS += 1

    if not a or not b:
        return 0
    if a[-1] == b[-1]:
        return 1 + lcs_length_naive(a[:-1], b[:-1])
    return max(lcs_length_naive(a[:-1], b), lcs_length_naive(a, b[:-1]))


print(lcs_length_naive("TRACE", "CRATE"), NAIVE_CALLS)
NAIVE_CALLS = 0
print(lcs_length_naive("ABCDEFGH", "IJKLMNOP"), NAIVE_CALLS)

3 44
0 25739

Two eight-letter strings with nothing in common cost 25,739 calls to produce the answer 0, when there are only 81 distinct questions to ask. functools.lru_cache closes that gap for free — as long as you recurse on indices rather than sliced strings, so the cache key stays small and the slicing does not copy.

from functools import lru_cache


def lcs_length_memo(a: str, b: str) -> tuple[int, int]:
    """The same recursion, but each (i, j) pair is solved once and remembered."""
    calls = 0

    @lru_cache(maxsize=None)
    def solve(i: int, j: int) -> int:
        nonlocal calls
        calls += 1
        if i == 0 or j == 0:
            return 0
        if a[i - 1] == b[j - 1]:
            return solve(i - 1, j - 1) + 1
        return max(solve(i - 1, j), solve(i, j - 1))

    return solve(len(a), len(b)), calls


print(lcs_length_memo("TRACE", "CRATE"))
print(lcs_length_memo("ABCDEFGH", "IJKLMNOP"))

(3, 23)
(0, 80)

25,739 calls became 80 — one for every cell of the 9 by 9 grid except (0, 0), which nothing ever asks about.

Memoisation is the honest translation of the recurrence, but the bottom-up table is better here: no recursion limit, no call overhead, and — the part that matters — a table you can walk backwards afterwards.

from collections.abc import Sequence


def lcs_table(a: Sequence, b: Sequence) -> list[list[int]]:
    """Build the table whose cell [i][j] is the LCS length of a[:i] and b[:j].

    Row 0 and column 0 stay zero: an empty prefix shares nothing with anything.
    Every other cell reads only cells above it and to its left, so filling the
    table row by row always finds its dependencies already computed.
    """
    rows, columns = len(a) + 1, len(b) + 1
    table = [[0] * columns for _ in range(rows)]

    for i in range(1, rows):
        for j in range(1, columns):
            if a[i - 1] == b[j - 1]:
                # The matched pair is worth 1, plus the best of both shorter prefixes.
                table[i][j] = table[i - 1][j - 1] + 1
            else:
                # No pair to take, so drop one element from one side and keep the best.
                table[i][j] = max(table[i - 1][j], table[i][j - 1])

    return table


def show_table(a: str, b: str, table: list[list[int]]) -> None:
    """Print the table with both strings as headers. '.' marks the empty prefix."""
    print("      " + "  ".join("." + b))
    for label, row in zip("." + a, table):
        print(f"   {label}  " + "  ".join(str(value) for value in row))


show_table("TRACE", "CRATE", lcs_table("TRACE", "CRATE"))

      .  C  R  A  T  E
   .  0  0  0  0  0  0
   T  0  0  0  0  1  1
   R  0  0  1  1  1  1
   A  0  0  1  2  2  2
   C  0  1  1  2  2  2
   E  0  1  1  2  2  3

Every number matches the hand-worked rows above. Now the backtrack, which is the part most write-ups skip.

def longest_common_subsequence(a: str, b: str) -> str:
    """Return one longest common subsequence of a and b.

    Ties are broken towards the upper cell, so a different but equally long
    answer exists whenever table[i - 1][j] equals table[i][j - 1].
    """
    table = lcs_table(a, b)
    i, j = len(a), len(b)
    picked: list[str] = []

    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            picked.append(a[i - 1])
            i -= 1
            j -= 1
        elif table[i - 1][j] >= table[i][j - 1]:
            i -= 1
        else:
            j -= 1

    # The walk runs from the end of both strings backwards, so undo that.
    return "".join(reversed(picked))


print(longest_common_subsequence("TRACE", "CRATE"))
print(longest_common_subsequence("AGGTAB", "GXTXAYB"))
print(repr(longest_common_subsequence("", "ANYTHING")))
print(longest_common_subsequence("PYTHON", "PYTHON"))

RAE
GTAB
''
PYTHON

If you only need the length, you never need the whole table. Each row reads nothing but the row directly above it and the cells to its own left, so two rows are enough.

def lcs_length(a: Sequence, b: Sequence) -> int:
    """LCS length using two rows instead of the whole table."""
    if len(b) > len(a):
        # Rows are len(b) + 1 wide, so put the shorter sequence on the columns.
        a, b = b, a

    previous = [0] * (len(b) + 1)

    for item in a:
        current = [0] * (len(b) + 1)
        for j in range(1, len(b) + 1):
            if item == b[j - 1]:
                current[j] = previous[j - 1] + 1
            else:
                current[j] = max(previous[j], current[j - 1])
        previous = current

    return previous[-1]


print(lcs_length("TRACE", "CRATE"), lcs_length("AGGTAB", "GXTXAYB"))
print(lcs_length("ABCDE" * 400, "EDCBA" * 400))

3 4
799

That last call compares two 2,000-character strings. The full table would be 4,000,000 cells; this version holds 4,002 integers at any moment and gets the same number.

How the code maps to the idea

The table is one bigger than the strings in both directions. Row 0 and column 0 are the empty prefix, which is why they are zero and why the loops start at 1. It is also why the code says a[i - 1] and not a[i]: row i is about the first i characters, so the newest sits at index i - 1. This off-by-one is the most common bug in DP-table code, and the fix is to say what a row means out loud before writing the loop.

Filling row by row is safe because every cell depends only on cells above and to the left, which are final by the time you arrive. Column by column works equally well.

On a match, the code ignores the neighbours, and it is right to. If the last elements are equal, some longest common subsequence ends with that pair: a candidate using neither gets one longer by appending it, so it was not longest; and a candidate matching one of them to something further back can be re-pointed at the pair without changing length. Checking the neighbours too is not wrong, just wasted work. On a mismatch there is no such shortcut, and max is simply "try both, keep the better".

The backtrack reads the table, it never recomputes. It asks only which rule could have produced each number, and the table's shape answers that. The >= on the tie is arbitrary but deterministic; flip it to > for a different, equally valid subsequence.

Edge cases fall out of the loop bounds. Empty input makes range(1, 1) empty, so the table stays zero and the backtrack never runs — hence ''. Identical inputs match on every diagonal step. And because lcs_table only indexes and compares, it works unchanged on lists or tuples of any comparable items, which is what the diff below needs.

Complexity

Time: O(n × m), always. The table has (n + 1)(m + 1) cells. Each does one equality test and then either an addition or a two-way max — constant time, assuming element comparison is constant time, which holds for characters and not for whole strings compared element by element. So the work is proportional to the cell count. There is no best or worst case worth naming, because the loops do not care what the data looks like: two identical 1,000-character strings cost the same 1,000,000 cell updates as two with nothing in common.

Backtracking: O(n + m). Every step decreases i, or j, or both. It starts at i + j = n + m and stops at 0, so it takes at most n + m steps — free next to building the table.

Without memoisation: exponential. With no elements in common there are no matches, so every call spawns two. The call count for lengths n and m is exactly 2 × C(n + m, n) - 1; it counts paths through the grid rather than cells. For the two 8-letter strings above that is 25,739, matching the counter. For two 20-character strings it is about 275 billion, against a table of 441 cells.

Space: O(n × m) for the full table, O(min(n, m)) for the length alone. A 2,000 by 2,000 table of Python integers costs about 32 MB in list pointers alone, before the integer objects. The two-row version keeps 2 × (min(n, m) + 1) integers, which is why it swaps its arguments first: you want the shorter sequence along the columns.

The catch is that two rows cannot backtrack — the path lives in the rows you discarded. If you need the sequence and linear space, use Hirschberg's algorithm (1975): a forward and a backward linear-space pass find where the optimal path crosses the middle row, then it recurses on the two halves. Same O(n × m) time, O(min(n, m)) space, roughly twice the constant factor.

Nobody knows anything substantially faster in general, either: under the Strong Exponential Time Hypothesis, LCS cannot be computed in O(n^(2 - e)) time for any positive e, a 2015 result of Abboud, Backurs and Williams. The quadratic table is not a placeholder for something cleverer.

When to use it, and when not to

Use it when you need the longest ordered but non-contiguous overlap between two sequences — two versions of a file, two DNA strands, two lists of events — and n × m is comfortable. A few thousand elements each is fine in Python; a few hundred thousand is not.

Not when you actually wanted a substring. Longest common substring is a different recurrence: on a mismatch the cell becomes 0 instead of the max of its neighbours, and the answer is the largest value anywhere in the table rather than the corner. For TRACE and CRATE it gives RA, length 2.

Not when you want substitutions. LCS only understands inserting and deleting. If changing one character into another should cost 1 rather than 2, you want Levenshtein distance — the same grid with a third option in the min. The two are directly related: with insert-and-delete edits only, the cheapest script has length n + m - 2 × LCS.

Not on two large, nearly identical files, where the answer is almost the whole file and the table is almost all waste. Myers' algorithm gets the same information in O((n + m) × D) time, D being the size of the edit script — tiny for a one-line change in a 5,000-line file. Hunt–Szymanski is the other classic escape at O((r + n) log n), r counting matching element pairs, which wins when matches are rare.

Not first, in Python. For text, difflib ships with the language and is written for the job. It does not compute an LCS, though: difflib.SequenceMatcher recursively finds the longest contiguous matching block and repeats on what is left either side — the Ratcliff/Obershelp method — which usually agrees with LCS and sometimes does not.

Where it shows up in the real world

diff, and so every code review you have ever read. The original Unix diff (Hunt and McIlroy, Bell Labs, 1976) computed a longest common subsequence of the two files' lines, each line hashed to one comparable token, and reported everything outside it as deleted or added. That is still how a diff is defined: the lines you keep form a common subsequence, and the best diff keeps the most.

Be precise about modern tools, though. git diff does not run this table by default — it uses Myers' 1986 O(ND) algorithm, which searches for a shortest edit script. For scripts of insertions and deletions the two problems are duals: a script of length n + m - 2L corresponds to a common subsequence of length L, so minimising one maximises the other. Git also ships --patience and --histogram, tuned for readable hunks rather than merely minimal ones.

Here is the LCS version, complete.

def diff(old: Sequence[str], new: Sequence[str]) -> list[str]:
    """Walk the table backwards, emitting a kept, added or deleted line each step."""
    table = lcs_table(old, new)
    i, j = len(old), len(new)
    output: list[str] = []

    while i > 0 or j > 0:
        if i > 0 and j > 0 and old[i - 1] == new[j - 1]:
            output.append("  " + old[i - 1])
            i -= 1
            j -= 1
        elif j > 0 and (i == 0 or table[i][j - 1] >= table[i - 1][j]):
            output.append("+ " + new[j - 1])
            j -= 1
        else:
            output.append("- " + old[i - 1])
            i -= 1

    return list(reversed(output))


before = [
    "def total(items):",
    "    result = 0",
    "    for item in items:",
    "        result += item",
    "    return result",
]
after = [
    "def total(items):",
    "    result = 0",
    "    for item in items:",
    "        result += item.price",
    "    print(result)",
    "    return result",
]

for line in diff(before, after):
    print(line)

  def total(items):
      result = 0
      for item in items:
-         result += item
+         result += item.price
+     print(result)
      return result

Four lines are common to both versions and print unchanged; the edited line shows as a delete plus an add, and the new print shows as an add. Nothing compared file contents beyond == on whole lines.

Sequence alignment in biology. Needleman–Wunsch (1970), the standard global alignment of two DNA or protein sequences, is this table generalised: replace "add 1 on a match" with a scoring matrix and "take the max neighbour" with a gap penalty. LCS is Needleman–Wunsch with match = 1, mismatch = 0 and no gap cost. Smith–Waterman is the same idea for local alignment.

Similarity scoring. ROUGE-L, a standard metric for evaluating machine-generated summaries, is defined directly as the LCS length between candidate and reference, normalised by their lengths. For plagiarism detection at scale, note that production systems mostly do not run LCS over raw documents — quadratic cost per pair is fatal across a corpus, so tools like MOSS fingerprint documents first and only compare candidates sharing fingerprints.

That difflib solves a different problem is easy to see directly:

import difflib

matcher = difflib.SequenceMatcher(None, "AAAA", "ABAA", autojunk=False)
matched = sum(block.size for block in matcher.get_matching_blocks())
print(matched, lcs_length("AAAA", "ABAA"))

2 3

AAA is a common subsequence of length 3, but the longest contiguous block is 2, and committing to it leaves nothing usable either side. Fine for a human-readable diff, wrong when you specifically need a longest common subsequence.

Common mistakes

Solving for substrings by accident. If the mismatch branch sets the cell to 0 instead of max(above, left), you have written longest common substring. Both are useful; know which one is running.

Getting the index offset wrong. Cell [i][j] is about a[i - 1] and b[j - 1]. Writing a[i] reads one character too far and raises IndexError on the last row.

Storing strings in the table instead of numbers. Putting the subsequence itself in each cell to skip the backtrack multiplies memory by the length of the answer and turns O(1) cell work into an O(k) concatenation. Store integers, walk backwards.

Backtracking after optimising the space away. The two-row version is correct for the length and useless for the sequence, because the rows the path needs are gone. Keep the table or use Hirschberg's algorithm.

Forgetting to reverse. The backtrack collects letters from the end towards the start, so EAR comes out instead of RAE — a wrong answer of exactly the right length, which a length-only test will never catch.

Practice

1. Return the length of the longest common substring by changing one line of the recurrence, and confirm it gives RA for TRACE and CRATE.
2. Compute the shortest common supersequence length — the shortest string containing both inputs as subsequences — from len(a), len(b) and the LCS length alone, then verify it by construction.
3. Extend the table to three strings and find the LCS of ABCD, ACBD and ADCB. Work out the time and space cost before writing it.
4. Count how many distinct longest common subsequences two strings have, using a second table filled alongside the first.
5. Implement Hirschberg's algorithm: split a in half, use two linear-space passes to find where the optimal path crosses that midpoint, and recurse on both halves.

Summary

Longest common subsequence is the cleanest introduction to dynamic programming, because the recurrence is two lines and the table is small enough to check by hand. Its real lesson is the second half: the filled table holds every answer, and walking backwards through it turns a number into the thing the number counted. That backtracking step is what makes DP produce solutions rather than scores, and it reappears in knapsack, in edit distance, and in every diff you read.

Keep reading

• Dynamic Programming Explained — the general method behind the table, and how to spot a problem that wants it.
• Edit Distance (Levenshtein) — the same grid with substitutions allowed, and the closest sibling to this post.
• The 0/1 Knapsack Problem — a two-dimensional table where the backtrack recovers which items you chose.
• The Coin Change Problem — where a greedy shortcut looks right and quietly is not.
• Big O Notation — the counting arguments used above, from first principles.