Longest Common Subsequence (LCS) Explained for Text Diffing

The Longest Common Subsequence (LCS) of two sequences is the longest ordered list of items that appears in both, without needing to be next to each other. It is the single idea behind almost every diff tool: once you know the longest run of lines or characters two files share, everything outside that run is exactly what changed. This guide explains LCS from scratch — what it is, how the dynamic-programming solution works step by step, and why it is the mathematical backbone of every tool that lets you compare text online.

Subsequence vs. Substring: The Difference That Matters

Before LCS makes sense, one distinction has to be crystal clear, because it trips up almost everyone at first.

• A substring is a contiguous block. In COMPARE, the letters OMP form a substring — they sit next to each other.
• A subsequence keeps the order but allows gaps. In COMPARE, the letters CMR form a subsequence — they appear in that order, but with other letters in between.

So a subsequence is the looser idea: pick items from the sequence, skip whatever you like, but never reorder what you keep. The common subsequence of two sequences is a subsequence that exists in both. The longest such subsequence is the LCS. There can be more than one LCS of the same maximum length, and that is fine — any of them works.

Why LCS Is the Heart of a Diff

So how does a textbook algorithm end up powering the tool you use to compare two documents? It comes down to one question a diff really asks: what stayed the same, and what didn't?

The parts that stayed the same, in order, are the longest common subsequence. Once a diff tool has the LCS, everything else follows on its own:

• Items in both files that belong to the LCS → unchanged.
• Items in the first file but not in the LCS → removed.
• Items in the second file but not in the LCS → added.

That is the whole trick. A line-by-line diff runs LCS over the lines of two files; a word-level diff runs it over the words. Keeping the common part as long as possible is the same as showing as few edits as possible, and that is what makes a diff look clean instead of lighting up half the file for no reason.

Solving LCS with a Dynamic Programming Table

The naive way to find the LCS — trying every possible subsequence — is exponential and hopeless for real files. Dynamic programming solves it in a single pass over a grid. The idea: build a table where each cell answers a smaller version of the same question, then reuse those answers instead of recomputing them.

Let the two sequences be X = ABCBDAB and Y = BDCAB. We build a table L where L[i][j] holds the length of the LCS of the first i characters of X and the first j characters of Y. The rule for filling each cell is short:

if X[i] == Y[j]:
    L[i][j] = L[i-1][j-1] + 1        # characters match — extend the diagonal
else:
    L[i][j] = max(L[i-1][j], L[i][j-1])   # take the best of up or left

The first row and first column are all zeros (comparing against an empty string gives an LCS of length 0). Filling left-to-right, top-to-bottom gives this completed grid — the number in the bottom-right corner, 4, is the length of the LCS:

Reading the Answer Back: Traceback

The grid gives the length of the LCS, but the diff needs the actual items. You recover them by walking backwards from the bottom-right cell:

• If the two characters at this cell match, that character is part of the LCS — record it and move diagonally up-left.
• If they don't match, move toward whichever neighbor (up or left) holds the larger value.

Collect the matched characters and reverse them. For ABCBDAB and BDCAB, the traceback spells out BCAB. Those four characters are the "unchanged" spine of the comparison; everything else is an insertion or a deletion.

Time and Space Complexity

The table has m × n cells for sequences of length m and n, and each cell costs constant work, so:

That O(m × n) memory is the catch. Comparing two 100,000-line files with the full-table method would need a grid of ten billion cells — which is exactly why production diff tools do not use the plain DP table for large inputs.

From LCS to Real Diff Tools: Myers and Beyond

LCS is the definition of an optimal diff, but the plain table is too memory-hungry to run on big files. This is where practical algorithms come in. The Myers diff algorithm finds the same shortest edit script far more efficiently — it runs in O(ND) time, where D is the number of edits, so when two files are similar (small D), it is dramatically faster and lighter than the full grid. Most tools you know, including Git, are built on Myers or a close variant.

Other algorithms trade optimality for readability. Patience diff anchors on lines that appear exactly once in both files, which often produces a more human-looking result for source code. But every one of them is chasing the same target LCS defines: keep the common part as long as possible, and show the smallest set of changes. Understanding LCS is understanding what all of them are trying to compute.

Frequently Asked Questions

What is the longest common subsequence in simple terms?

It is the longest ordered list of items — characters, words, or lines — that appears in both sequences, allowing gaps but not reordering. For "ABCBDAB" and "BDCAB", the LCS is "BCAB". In diffing, the LCS is the part of two files that stayed the same.

What is the difference between a subsequence and a substring?

A substring is contiguous (its characters are next to each other); a subsequence keeps order but allows gaps between characters. "OMP" is a substring of "COMPARE"; "CMR" is a subsequence of it. LCS uses the subsequence definition.

How is LCS used in diff tools?

A diff tool computes the LCS of two files. Items in the LCS are unchanged, items only in the first file are deletions, and items only in the second file are additions. Maximizing the LCS is the same as showing the fewest edits.

What is the time complexity of the LCS algorithm?

The dynamic-programming solution runs in O(m × n) time for sequences of length m and n. It also uses O(m × n) space for the full table, though the length alone can be found in O(min(m, n)) space using two rows.

Why don't large diff tools use the LCS table directly?

Because the table needs O(m × n) memory. For two very large files that is billions of cells. Tools use the more efficient Myers O(ND) algorithm instead, which computes the same result without building the whole grid.

Can two sequences have more than one LCS?

Yes. Two sequences can have several different subsequences that all reach the maximum length. Any of them is a valid LCS, and different tools may report different ones while still being correct.