Longest Common Subsequence

Every time you run git diff, ask a DNA sequencer to find how two genes diverged, or let a text editor highlight what changed between two versions of a file, a single algorithm is doing the heavy lifting: Longest Common Subsequence (LCS).

The question is almost childishly simple. Given two strings — say, ABCBDAB and BDCABA — what is the longest sequence of characters that appears in both, in the same relative order, without rearranging anything? You don't have to pick consecutive characters; you just can't swap them around. For those two strings the answer is BCBA or BCAB (length 4): four characters appear in both strings, left-to-right, in matching order.

The naive approach — try every subsequence of the first string and check it against the second — takes exponential time. But this problem was solved in 1974 when researchers discovered a beautiful table-filling trick. Today it runs in $O(mn)$ time (where m and n are the string lengths), fast enough that diff tools apply it to thousands of lines in milliseconds.

LCS sits in P: it is definitively easy. What makes it worth studying is how elegantly dynamic programming turns an exponential search into a polynomial one — and how the same idea echoes through bioinformatics, version control, and spelling correction.

Type two strings below and press Compute LCS. The table fills cell by cell — each entry records the length of the longest common subsequence of the prefixes seen so far. When the table is full, the algorithm traces a path back through it to read off the actual shared characters.

<div class="controls">
  <label>{{label_a}} <input id="strA" type="text" value="ABCBDAB" maxlength="12" /></label>
  <label>{{label_b}} <input id="strB" type="text" value="BDCABA" maxlength="12" /></label>
  <div class="btns">
    <button id="compute" type="button">{{btn_compute}}</button>
    <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
</div>
<div id="result" class="result"></div>
<div id="table-wrap" class="table-wrap"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.controls { display: flex; flex-wrap: wrap; gap: .6rem; align-items: flex-end; margin-bottom: .8rem; }
label { display: flex; flex-direction: column; gap: .2rem; font-size: .85rem; font-weight: 600; color: #444; }
input { font: 700 15px ui-monospace, monospace; padding: .35rem .5rem; border: 1px solid #bcc0c6;
        border-radius: 6px; width: 160px; letter-spacing: .08em; }
.btns { display: flex; gap: .4rem; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .8rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 6px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.result { font-size: 1rem; font-weight: 700; min-height: 1.6em; margin-bottom: .7rem; color: #0a7d33; }
.table-wrap { overflow-x: auto; }
table { border-collapse: collapse; font-size: .82rem; }
th, td { width: 32px; height: 32px; text-align: center; border: 1px solid #dde2e8; }
th { background: #edf1f5; font-weight: 700; font-family: ui-monospace, monospace; color: #1d3557; }
td { font-family: ui-monospace, monospace; }
td.match { background: #d4edda; color: #0a5523; font-weight: 700; }
td.path  { background: #cde4f5; }
td.path.match { background: #a8d8a0; }
td.arrow { font-size: .7rem; color: #888; vertical-align: bottom; line-height: 1; }

// Code not found

Notice how the diagonal arrows mark the matches: every time both strings share a character in the same relative position, the LCS length ticks up by one. Horizontal and vertical arrows mean "skip a character" from one string or the other. The final answer sits in the bottom-right corner of the table.

LCS is definitively solved — proved to be in the complexity class P by the dynamic programming algorithm published by Wagner and Fischer (1974) and refined by Hunt and Szymanski (1977).

Here is why the naive approach fails and the DP table succeeds:

• Brute force: the first string of length m has 2ᵐ subsequences. Checking each one against the second string takes $O(n)$ time. Total: $O(n \cdot 2ᵐ)$ — exponential, completely impractical for strings of any real length.
• The key insight (optimal substructure): if the last characters of both strings match, they must be in the LCS. If they don't match, the LCS comes from either dropping the last character of the first string or the last character of the second. This single observation turns the problem into a recurrence: LCS(i, j) = LCS(i−1, j−1) + 1 if the characters match, otherwise max(LCS(i−1, j), LCS(i, j−1)).
• Memoization / the table: there are only m × n distinct sub-problems. Fill them once, in order, and each entry takes $O(1)$ to compute. Total: $O(mn)$ time and $O(mn)$ space.
• Space optimization: if you only need the length (not the actual subsequence), you can get away with O(min(m, n)) space by keeping only two rows of the table at a time.

A subtle hardness result lives nearby: the Longest Common Substring problem (characters must be consecutive) is also in P, but finding the LCS of three or more strings simultaneously is NP-hard in general. And the related Shortest Common Supersequence problem (the shortest string that contains both strings as subsequences) is also solvable in $O(mn)$ using the same DP table. Compare this with sequence alignment, which adds gap penalties, or edit distance, which counts insertions, deletions, and substitutions.

LCS is one of those algorithms that quietly runs inside half the software you use every day:

• Version control (git diff, patch): diff tools find the LCS of two files line by line. Lines in the LCS are "unchanged"; everything else is an insertion or deletion. This is what the + and $-$ markers mean.
• Bioinformatics and DNA alignment: two DNA strands diverged from a common ancestor. The LCS of their base sequences reveals the conserved regions — the parts evolution left untouched. The same idea, scaled up, drives tools like BLAST and Clustal.
• Plagiarism detection: shared long subsequences between two documents are strong evidence that one copied from the other, even if words were rearranged locally.
• Spell checking and fuzzy matching: edit distance (the minimum edits to turn one string into another) is computed from the LCS length: edit distance = m + n − 2 × LCS(m, n). Your spell checker uses this every time it ranks suggestions.
• File merging: three-way merge in version control systems uses the LCS of each branch against the common ancestor to decide what to keep, what to add, and what conflicts need a human to resolve.

The algorithm's reach extends far beyond strings: any time you need to find the longest "common skeleton" between two ordered sequences — of events, of moves, of musical notes — LCS is your tool.

Longest Common Subsequence is a rare thing in complexity theory: a problem that looks exponential — every possible subsequence, every possible pairing — but turns out to be completely tame, sitting firmly in P.

The key was seeing that the problem has optimal substructure: every solution is built from smaller solutions, and the small solutions can be computed once and stored. Fill a table, read off the answer, trace back the path. The entire idea fits on a whiteboard and runs in milliseconds on any modern device.

That simplicity is deceptive. The same DP table that answers "what do these two strings share?" underlies git diff, genome alignment, spell correction, and plagiarism detection — technologies that touch billions of people every day.

So next time git diff shows you exactly which lines changed, remember: it's not magic. It's an $O(mn)$ table-filling algorithm, solved half a century ago, quietly making the modern software world legible. Compare with sequence alignment and pattern matching for related solved problems, or step up to P vs NP to see why not every such question has such a clean answer.