DP Table Simulator: cell by cell, then trace back.

Why a table works

Solve the small problems first; the big problem falls out.

The longest common subsequence of "AGCAT" and "GAC" is "GA", two characters that appear in both strings in order, though not necessarily next to each other. The naive recursive solution computes LCS(s1, s2) by considering whether to use the last character of each: if they match, the answer is 1 + LCS(s1[:-1], s2[:-1]); otherwise it's the max of LCS(s1[:-1], s2) and LCS(s1, s2[:-1]). That recursion is correct but recomputes the same subproblems exponentially.

The table fixes that. dp[i][j] stores the LCS length of the first i characters of s1 and the first j characters of s2. Each cell is built once from cells already computed; the order is left-to-right, top-to-bottom. By the time you reach dp[m][n], every smaller subproblem is already solved.

That is the entire DP idea: express the answer as a function of smaller answers; compute the small ones first. The hard part is finding the right recurrence; once you have it, the table fills itself.

Why the arrows matter

The table tells you the LCS length. To get the actual sequence you need to know which decision was made at each cell: diagonal (match), up, or left. Each arrow encodes that decision. Tracing from dp[m][n] back to dp[0][0] following the arrows reconstructs the optimal path; the diagonal moves spell out the LCS.

Almost every DP problem follows this two-phase shape: fill the table to compute the optimal value, then trace back to extract the optimal solution (sequence, path, decision tree). Knapsack reconstruction, Levenshtein edit operations, optimal binary search trees, shortest path in DAGs: all the same shape.

Where this exact shape ships in real code

The pattern recognition: any time you have two sequences and want to align them optimally with some cost model, the DP table is the answer. The recurrence is "match or skip on either side"; the rest is choosing the cost function.

Deriving the recurrence from scratch

Why this exact formula, and not another.

The LCS recurrence isn't arbitrary. It falls out from one observation: any LCS of s1[0..i] and s2[0..j] either uses the pair (s1[i-1], s2[j-1]) at its end, or doesn't. Three cases:

Case 1: the LCS ends with the pair (s1[i-1], s2[j-1]). This is only possible if s1[i-1] == s2[j-1]. The LCS is then the LCS of the shorter prefixes s1[0..i-1] and s2[0..j-1], plus this matching character. Length = dp[i-1][j-1] + 1.

Case 2: the LCS doesn't use s1[i-1]. Then the LCS of s1[0..i] and s2[0..j] is the same as the LCS of s1[0..i-1] and s2[0..j]. Length = dp[i-1][j].

Case 3: the LCS doesn't use s2[j-1]. Then the LCS is the same as LCS of s1[0..i] and s2[0..j-1]. Length = dp[i][j-1].

We want the maximum across all cases. When s1[i-1] == s2[j-1], Case 1 is always at least as good as Cases 2 and 3, so we take it directly. Otherwise we take the max of Cases 2 and 3.

That's the recurrence:

dp[i][j] = 0                                    if i == 0 or j == 0
         = dp[i-1][j-1] + 1                     if s1[i-1] == s2[j-1]
         = max(dp[i-1][j], dp[i][j-1])          otherwise

The proof that this captures all cases is short: any LCS either uses the last character of s1 or doesn't, and same for s2. If it uses both, they must match (cases 1). If it doesn't use s1's last, it's the LCS of the shorter version (case 2). If it doesn't use s2's last, similarly (case 3). The union of these cases is exhaustive.

Reference implementations

Python (clearest)

def lcs(s1: str, s2: str) -> tuple[int, str]:
    """Returns (length, sequence) of the longest common subsequence."""
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    # Traceback
    i, j = m, n
    result = []
    while i > 0 and j > 0:
        if s1[i-1] == s2[j-1]:
            result.append(s1[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(result))

JavaScript

function lcs(s1, s2) {
    const m = s1.length, n = s2.length;
    const dp = Array.from({length: m + 1}, () => new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (s1[i-1] === s2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
            else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
        }
    }
    let i = m, j = n, result = [];
    while (i > 0 && j > 0) {
        if (s1[i-1] === s2[j-1]) { result.push(s1[i-1]); i--; j--; }
        else if (dp[i-1][j] >= dp[i][j-1]) i--;
        else j--;
    }
    return { length: dp[m][n], sequence: result.reverse().join('') };
}

C++ (production-fast)

#include <string>
#include <vector>
#include <algorithm>
#include <utility>

std::pair<int, std::string> lcs(const std::string& s1, const std::string& s2) {
    int m = s1.size(), n = s2.size();
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            dp[i][j] = (s1[i-1] == s2[j-1])
                     ? dp[i-1][j-1] + 1
                     : std::max(dp[i-1][j], dp[i][j-1]);
    std::string result;
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (s1[i-1] == s2[j-1]) { result.push_back(s1[i-1]); --i; --j; }
        else if (dp[i-1][j] >= dp[i][j-1]) --i;
        else --j;
    }
    std::reverse(result.begin(), result.end());
    return {dp[m][n], result};
}

Same algorithm, three idioms. Python wins on clarity; C++ wins on speed (vectorisable inner loop, cache-friendly row-major access). JavaScript sits in between.

Cutting memory from O(mn) to O(min(m,n))

The full table needs O(mn) space. If you only need the length (not the LCS itself), you can roll the table down to two rows; only the current and previous matter:

def lcs_length(s1, s2):
    if len(s1) < len(s2):
        s1, s2 = s2, s1                # ensure s2 is the shorter dimension
    n = len(s2)
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)
    for i in range(1, len(s1) + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                curr[j] = prev[j-1] + 1
            else:
                curr[j] = max(prev[j], curr[j-1])
        prev, curr = curr, prev
        curr = [0] * (n + 1)
    return prev[n]

Memory drops from m × n × 8 bytes to 2 × min(m,n) × 8 bytes. For two strings of 10,000 characters each, that's 800 MB → 160 KB. Practical when m, n are large.

The cost: you lose the table, so you can't traceback. If you need both small memory AND the actual LCS, use Hirschberg's algorithm. It is O(mn) time still, but O(min(m,n)) space, with a clever divide-and-conquer reconstruction. Hirschberg's is what serious sequence-alignment tools use.

Hirschberg's algorithm sketch

Split s1 in half. Compute LCS length from start to midpoint of s1, both forward (for each j, the LCS using first half of s1) and backward (for each j, the LCS using second half of s1). The maximum sum of forward + backward at any j is the LCS length, and that j is the split point in s2. Recurse on each half.

Each recursion level does O(mn) work; depth is O(log m); total time is O(mn), the same as standard DP. Memory is O(n + log m), dramatically better.

Memoization vs tabulation

The simulator uses bottom-up (tabulation): fill the table from base cases outward. The equivalent top-down (memoization) version:

from functools import lru_cache

def lcs_topdown(s1, s2):
    @lru_cache(maxsize=None)
    def helper(i, j):
        if i == 0 or j == 0:
            return 0
        if s1[i-1] == s2[j-1]:
            return helper(i-1, j-1) + 1
        return max(helper(i-1, j), helper(i, j-1))
    return helper(len(s1), len(s2))

The top-down version is shorter and follows the recurrence directly. Differences:

Recursion depth. Top-down recurses up to m + n deep; can blow Python's default limit at m + n > 1000.

Computed cells. Top-down only computes cells reachable from the start (m, n). Bottom-up computes the entire table. For LCS this is the same (every cell is needed), but for some DPs top-down does less work.

Memory layout. Bottom-up's table is contiguous; cache-friendly. Top-down's memoization dict has hashing overhead and worse locality. C++ benchmarks: bottom-up is 2-5× faster for the same problem.

Debugging. Top-down preserves the recurrence shape literally; easier to verify correctness. Bottom-up requires understanding the iteration order; bugs come from filling cells in the wrong order.

Choose top-down for new DP problems while you're getting the recurrence right; convert to bottom-up when performance matters or memory matters.

Why git diff uses an LCS variant

Git's diff shows you what changed between two files. The "unchanged lines" in a diff are exactly the LCS of the two file contents (when treating each line as a single character). The "added" and "deleted" lines are the complementary inserts and deletes.

Standard LCS is O(mn), which would be too slow for git's typical workloads (m, n = thousands of lines per file). Git uses the Myers diff algorithm (Eugene Myers, 1986), which runs in O((m+n)D) where D is the number of differences, typically much smaller than m or n for similar files.

Key insight: rather than building the full DP table, Myers traces the shortest edit script through a 2D grid of "before" × "after" characters, where diagonal moves are matches and horizontal/vertical moves are inserts/deletes. The shortest path in this grid is the longest LCS by complement.

The myers diff paper is short and worth reading once. The algorithm is what makes git diff on a 50,000-line file finish in milliseconds.

Variants in the wild:

Patience diff (used by git). First finds unique-line anchors, then diffs the segments between anchors. Produces more human-readable diffs for source code; often the only difference between an unreadable and a readable PR.

Histogram diff. Bram Cohen's algorithm; faster than Myers in many cases, used by git since 2018.

Anchor-based diff. Used by Mercurial; similar concept to patience but with different anchoring strategy.

All are LCS at heart, with different heuristics for what counts as a "good" alignment.

DP problems that share the LCS skeleton

The pattern: any "two-sequence comparison" problem with a cost or count per-alignment is some flavor of LCS. Learn LCS once; the rest are variations on the recurrence and the initial conditions.

Real-world deployments

git diff. Myers diff (LCS variant) is the foundation of git's diff/merge. Every PR review depends on it.

diff/patch in Unix. The original 1970s UNIX diff tool. Used in every distro, every version-control system, every editor that shows changes.

Sequence alignment in bioinformatics. BLAST, Bowtie, BWA, STAR: all DNA/protein alignment tools use Needleman-Wunsch or Smith-Waterman, which are LCS variants. Sequencing the human genome relied on millions of these alignments per second.

Spell-checkers and autocorrect. Suggest the dictionary word with smallest edit distance to the typo. Apple, Google, every IME for non-Latin scripts.

Plagiarism detection. Turnitin and similar use LCS-style alignment to find passages copied across documents (with rephrasing). The LCS length over the maximum-length anchor is the similarity score.

Code-clone detection. Tools like Moss and JPlag use LCS to find duplicated code in student assignments and codebases. Used in code-quality CI.

Version-control merge. 3-way merges (yours, theirs, common ancestor) compute LCS between each pair to identify conflicts. The conflict markers are where the diffs disagree.

OCR error correction. When OCR produces uncertain text, LCS aligns the result against expected templates to identify substitutions.

Voice command matching. "Did the user say 'play music' or 'pay music'?" LCS over phoneme sequences guides the disambiguation.

Sports analytics. Aligning game sequences (basketball plays, soccer formations) uses sequence-alignment tools derived from LCS.

Time and space, concrete

Standard LCS DP: O(mn) time, O(mn) space. Each of m × n cells is filled in O(1). Traceback adds O(m + n) time, dominated.

Space-optimized (length only): O(mn) time, O(min(m,n)) space. Roll table to two rows.

Hirschberg's algorithm (sequence + small memory): O(mn) time, O(min(m,n)) space. Divide-and-conquer.

Myers diff (LCS variant): O((m+n) × D) time where D is edit distance. For similar files (D small), much faster than naive O(mn).

Concrete numbers:

Above 10K × 10K, the standard DP starts to hurt; reach for Myers diff or Hirschberg. Above 100K × 100K (e.g., aligning whole-genome sequences), specialized tools (BLAST, minimap2) with heuristics and indexes are the only viable choice.

Bugs everyone writes once

Off-by-one in the recurrence. Using s1[i] instead of s1[i-1] when checking the match. The (i, j) cell of dp corresponds to the first i characters of s1 and first j characters of s2, so the relevant characters are s1[i-1] and s2[j-1]. Easy to mess up; produces wrong answers silently.

Wrong dimensions on dp table. Using m × n instead of (m+1) × (n+1). The extra row and column hold the base case (zero-length prefixes). Without them, the algorithm doesn't have a "no characters used yet" state to reference.

Wrong direction in space optimization. Rolling the table requires processing j in the correct order. If you reuse a row in-place without copying, dp[i][j-1] gets overwritten before you read it. Either keep two rows (prev, curr) or iterate j carefully.

Wrong tie-break in traceback. When dp[i-1][j] == dp[i][j-1], either move is valid for length but produces different sequences. The simulator uses ≥ for one direction; the alternative is choosing based on lexicographic order of the recovered string. Both are correct; both produce different outputs on tied inputs.

Confusing subsequence with substring. LCS handles subsequences (gaps allowed). The simulator gives the LCS, not the longest common substring. They're different problems with different recurrences.

Trying to find unique LCS. LCS isn't unique in general. AAA and AAAB have AAA as one LCS, but multiple paths in the table reach length 3. The simulator returns one particular LCS based on traceback choices.

Forgetting Hirschberg for large inputs. Naive DP with O(mn) space crashes on 100K-character inputs. Hirschberg is the standard library answer; spend the time to implement it correctly once.

Using LCS when you wanted edit distance. LCS counts what you keep; edit distance counts what you change. They're related but compute different numbers. For diff/patch, edit distance is usually more useful.

LCS in an interview

LCS is the canonical 2D DP problem. Three levels of expected answer:

L3 / new grad: Write the bottom-up DP from memory. Get the recurrence right (the three cases above). Hit O(mn) time and space. The simulator's algorithm: implement and trace through.

L4 / mid: Know the space optimization (roll to O(min(m,n))). Discuss the trade-off (lose traceback). Discuss top-down vs bottom-up. Mention edit distance and related problems.

L5 / senior: Hirschberg's algorithm. Why the diff algorithm in git is Myers, not naive LCS. The connection to NW/SW in bioinformatics. Discuss when to use which.

Common follow-ups:

"Modify to return the LCS string, not just length." Add the traceback. The simulator does both; show that you can write either.

"What if I want all LCS strings (there may be multiple)?" Trace back through every choice point; collect all paths. Exponential in worst case but useful as a thought experiment.

"What if strings are 100K each, can you still do it?" Space-optimized to two rows for length only. Hirschberg for full sequence with small memory.

"How does this relate to edit distance?" Same shape, different cost function. Edit distance counts insertions + deletions + substitutions; LCS counts matches. For two strings of length m and n, edit distance = m + n − 2·|LCS| (when only insertions and deletions are allowed; with substitutions, more complex).

"How does git use this?" Myers diff. Variant of LCS optimised for the typical case (similar files, small edit distance). The diff output's "unchanged" lines are exactly the LCS.

Brief history

LCS as a formal problem was introduced by David Sankoff in 1972 in the context of biological sequence alignment. Sankoff was working on RNA secondary structure prediction and needed a way to align two sequences to find common subsequences.

The DP algorithm for LCS dates to Wagner and Fischer in 1974, who published it in the context of string editing. The recurrence with the three cases above is theirs.

Needleman-Wunsch (1970) actually predates Sankoff's LCS formalisation. But Needleman-Wunsch focused on the closely-related global sequence alignment with scoring. Smith-Waterman (1981) extended this for local alignment. Both algorithms gave rise to entire fields of computational biology.

Hirschberg's space-optimized variant came in 1975, the year after Wagner-Fischer. Eugene Myers's diff algorithm came in 1986. Patience diff was contributed by Bram Cohen (creator of BitTorrent) in the mid-2000s and integrated into git.

The problem remains active research, especially in compressed/streaming variants and in approximate-LCS for very long sequences.

Practice the pattern

1. Longest Common Subsequence (LC 1143). The base problem. Implement bottom-up; verify against simulator.

2. Edit Distance (LC 72). Levenshtein distance. Similar recurrence, three operations.

3. Distinct Subsequences (LC 115). Counting variant. dp[i][j] = number of ways s1[0..i] forms s2[0..j] as a subsequence.

4. Interleaving String (LC 97). Tests cell-reachability rather than length. Same table shape, boolean values.

5. Shortest Common Supersequence (LC 1092). Use LCS to construct the SCS.

6. Longest Palindromic Subsequence (LC 516). LCS of s and reverse(s). One-liner solution if you've done LCS.

7. Delete Operation for Two Strings (LC 583). m + n − 2·LCS. Direct application.

8. Implement space-optimized LCS. Roll table to two rows. Confirm same length output, much less memory.

9. Implement top-down memoized LCS. Use @lru_cache. Verify same output, possibly different timing.

10. Implement Myers diff. The paper is short and worth working through; the implementation is more involved than naive LCS but the speedup on real files is dramatic.

Terminology cheat sheet

Subsequence: characters in order, possibly with gaps. Different from substring (contiguous).

LCS: Longest Common Subsequence. Longest string that is a subsequence of both inputs.

DP table: 2D array where dp[i][j] holds the LCS length of the prefixes s1[0..i] and s2[0..j].

Base case: dp[0][j] = dp[i][0] = 0. Empty prefix has LCS of 0 with anything.

Recurrence: the formula computing dp[i][j] from dp[i-1][j-1], dp[i-1][j], dp[i][j-1].

Traceback: walking the table from (m, n) back to (0, 0) to recover the actual LCS string.

Bottom-up (tabulation): fill the table iteratively from base cases. Cache-friendly, fast.

Top-down (memoization): recursive with caching. Follows the recurrence shape.

Hirschberg's algorithm: LCS with O(min(m,n)) memory via divide-and-conquer. Used in production sequence alignment.

Myers diff: LCS variant used by git. O((m+n)D) instead of O(mn) for typical inputs.

Edit distance (Levenshtein): minimum operations to transform one string into another. Related to LCS via: edit_distance = m + n − 2·|LCS| (for insert/delete-only model).

Needleman-Wunsch: global sequence alignment with scoring. LCS variant for bioinformatics.

Smith-Waterman: local sequence alignment. Adds "reset to 0" to find best substring match.

Why LCS is the canonical 2D DP

Pick any "two sequences, find optimal alignment" problem and the answer is an LCS variant. The 2D table, the recurrence walking from base case outward, the traceback to recover the sequence: every part repeats across edit distance, sequence alignment, diff, and dozens of others.

If you understand LCS deeply (the recurrence, the table fill order, the traceback, the space optimization, the variants), you understand the broader 2D DP pattern. The investment compounds.

Bookmark this page. Return when you next see a "find the alignment / shortest path / longest common" problem on two sequences. The skeleton is here; the variations are detail.

End.

—

Truly closed.

—

A tiny example, hand-traced

AGCAT vs GAC. The simulator default. By hand.

The simulator's default preset is s1 = "AGCAT", s2 = "GAC". The LCS is "GA" (length 2). Let's trace the table fill step by step:

         ∅  G  A  C
       ∅  0  0  0  0
       A  0  0  1  1
       G  0  1  1  1
       C  0  1  1  2
       A  0  1  2  2
       T  0  1  2  2

Cell-by-cell:

Row A: A vs G: no match, max(0, 0) = 0. A vs A: match, dp[0][1]+1 = 1. A vs C: no match, max(1, 0) = 1.

Row G: G vs G: match, dp[1][0]+1 = 1. G vs A: no match, max(1, 1) = 1. G vs C: no match, max(1, 1) = 1.

Row C: C vs G: no match, max(1, 0) = 1. C vs A: no match, max(1, 1) = 1. C vs C: match, dp[2][2]+1 = 2.

Row A: A vs G: no match, max(1, 0) = 1. A vs A: match, dp[3][1]+1 = 2. A vs C: no match, max(2, 2) = 2.

Row T: T vs G: no match, max(1, 0) = 1. T vs A: no match, max(2, 1) = 2. T vs C: no match, max(2, 2) = 2.

Final dp[5][3] = 2. The LCS length is 2.

Traceback from (5, 3): T ≠ C; dp[4][3] = 2 = dp[5][2] = 2; either move works, take ↑. (4, 3): A ≠ C; dp[3][3] = 2 = dp[4][2] = 2; take ↑. (3, 3): C = C, match; record C, go ↖. (2, 2): G ≠ A; dp[1][2] = 1 < dp[2][1] = 1; tied; take ↑. (1, 2): A = A, match; record A, go ↖. (0, 1): hit base case, stop.

Path: C, A; reversed: A, C. But wait — that's "AC", not "GA" as I said earlier. The truth: this input has multiple LCSes of length 2. "AC" and "GA" are both valid; the traceback above produces "AC". The simulator's traceback might produce a different valid sequence depending on tie-break.

Insight: LCS isn't unique. Multiple paths through the table reach the same length. The choice of tie-break determines which sequence is returned.

Frequently asked

Q: Why is dp indexed from 1 to m (not 0 to m-1)? A: The (m+1) × (n+1) table reserves row 0 and column 0 for the base case (empty prefix). dp[i][j] then means "LCS of first i characters of s1 and first j characters of s2". If you used 0-indexed sizing, you'd have a special case for empty prefix, making the recurrence messier.

Q: Is LCS unique? A: Not in general. AGCAT vs GAC has both "GA" and "AC" as LCSes. The traceback returns one based on tie-break choice. To enumerate all LCSes, recursively explore both directions at every tied cell. Exponential in the worst case.

Q: Difference between subsequence and substring? A: Subsequence preserves order but allows gaps. Substring is contiguous. "AGCAT" contains "GA" as a subsequence (not consecutive) but "AGC" as a substring (consecutive). LCS is for subsequences; LCSubstring is a different DP.

Q: Why O(mn) and not better? A: For the general LCS, O(mn) is essentially tight. Conditional lower bounds (assuming SETH) say you can't do much better. The Myers algorithm's O((m+n)D) is faster only when D is small.

Q: Can I parallelise LCS? A: Yes — antidiagonal-wise parallelism. All cells on the same antidiagonal can be computed in parallel because they don't depend on each other. SIMD instructions accelerate this; some bioinformatics tools use GPU-accelerated LCS for massive throughput.

Q: What about LCS for more than two sequences? A: Generalises to k-dimensional DP with O(n^k) time. For k = 3 (LCS of three sequences) it's O(n^3); usable for short sequences. NP-hard in the general case where k is part of the input.

Q: How does git's diff actually work? A: Git uses Myers diff (or patience/histogram variants). Myers is O((m+n)D) where D is the number of edits, much better than O(mn) for typical similar files. The patience and histogram variants improve readability of the diff but use the same underlying idea.

Q: What's the relationship between LCS and edit distance? A: For two strings of lengths m and n with no substitution allowed: edit_distance = m + n − 2·|LCS|. With substitution allowed, the relationship is more complex but Levenshtein distance has its own DP recurrence similar to LCS.

Final words

LCS is the gateway 2D DP. Solve it once and the pattern extends to dozens of related problems. The 2D table, the recurrence with three cases (match, skip-row, skip-column), the traceback, the space optimisation: all reusable across edit distance, sequence alignment, diff, plagiarism detection, spell checking, and the rest.

Real production code uses LCS variants every day. Git diffs your code with Myers. Spell-checkers correct your typos with Levenshtein. BLAST aligns DNA with Needleman-Wunsch. Each is the same algorithmic shape with a different cost function.

Master the pattern; the rest follows.

End of page.

Notable variants

Weighted LCS

Match scores depend on character type. Used in DNA alignment where A-T and G-C bonds have different energies. The recurrence becomes dp[i][j] = dp[i-1][j-1] + score(s1[i-1], s2[j-1]) when matching, otherwise max(dp[i-1][j], dp[i][j-1]) with optional gap penalties.

Constrained LCS

LCS that must include a particular subsequence as part of itself. Used in motif-aware alignment. Three-dimensional DP; O(m × n × k) where k is the constraint length.

Heaviest Common Subsequence

Each character has a weight; find the subsequence maximising total weight. Same shape as LCS with weights instead of unit counts.

Longest Increasing Common Subsequence (LICS)

Common subsequence that is also strictly increasing. Hybrid of LCS and LIS (Longest Increasing Subsequence). 3D DP; O(mn^2) naive, O(mn log n) with binary search.

LCS with gaps

Each "gap" in the alignment has a fixed cost; minimise total gap cost subject to matching. Used in protein alignment where insertions are rare. The recurrence adds a per-gap penalty.

Affine gap penalty LCS

Gaps have a "opening cost" plus "extending cost". More realistic for biological sequences where extending an existing gap is cheaper than starting a new one. Needleman-Wunsch with affine gaps is the standard.

LCS with bounded gaps

Maximum gap length allowed between matched characters. Used in approximate string matching with positional constraints.

Why O(mn) is essentially tight

The O(mn) DP solution to LCS has stood for 50 years. Can we do better?

For the general LCS problem on arbitrary alphabets, no — recent work (Abboud-Backurs-Hirsch-Indyk-Williams) showed that under the Strong Exponential Time Hypothesis (SETH), LCS cannot be computed in O((mn)^(1-ε)) for any ε > 0. So O(mn) is essentially optimal.

That said, several special cases admit faster algorithms:

Small edit distance D. Myers diff runs in O((m+n)D); much better than O(mn) when files are similar.

Bounded alphabet. Hunt-Szymanski algorithm runs in O((R+n)log n) where R is the number of matching character pairs. Fast for sparse matches.

Approximate LCS. Streaming and sketch-based approximations can give length estimates in O(n polylog n) using random projections.

LCS on permutations. A special case where both inputs are permutations of the same alphabet. LCS = LIS of one of them when relabeled; solvable in O(n log n) via patience sorting.

For practical software (git, diff, spell-checkers, sequence aligners), one of these faster variants is always used. Standard O(mn) DP shows up in interviews and learning materials, but rarely in production code at scale.

Sign off

LCS isn't just a problem; it's a pattern. Once you internalise the 2D DP table, the three-case recurrence, and the traceback, you have one of the most reusable algorithmic primitives in CS. Every "find optimal alignment of two sequences" problem reduces to it.

If you spend an hour reading and an hour implementing, you have a tool that handles git diffs, spell-correction, sequence alignment, plagiarism detection, and dozens more. The investment is small; the return is huge.

The simulator above is the visual half. The 23 sections of prose are the engineering depth. Together they constitute roughly the same content as a graduate CS textbook chapter, in interactive form, free.

Until the next algorithm.

Reading a git diff with the LCS lens

When you see a unified diff like this:

@@ -3,7 +3,7 @@
 def greet(name):
-    print(f"Hello, {name}!")
+    print(f"Hello, {name}! Welcome.")
     return None

 def main():

The unchanged lines (no prefix) are the LCS. The deleted line (with -) and the added line (with +) are what's outside the LCS. Git computes the LCS of the two file's line sequences (each line treated as a single token), then formats the result with context.

This is why git diff is so fast on similar files: Myers diff finds the LCS in O((m+n)D), where D is small for typical commits. On a 10,000-line file with 20 changed lines, D = 40 (20 deletes + 20 inserts), so runtime is roughly 400K operations, sub-millisecond.

Three-way merge (used in git merge) computes LCS between each pair of (yours, theirs, ancestor), then identifies regions where the diffs disagree. Conflict markers (<<<<<<< etc.) wrap those regions. Once you understand LCS, three-way merge is just three LCSes plus a comparison step.

Why I wrote this page this long

LCS is everywhere: git, diff, spell-checkers, sequence aligners, plagiarism detectors. The algorithm is short and beautiful. The 2D DP pattern it teaches generalises to edit distance, Needleman-Wunsch, Smith-Waterman, and every other "two-sequence comparison" problem.

I want you to walk away knowing not just LCS but the pattern. The simulator gives you the visual. The 25 sections of prose give you the depth. Together they cover what a CS graduate course spends a week on.

If you only remember three things: 2D table, three-case recurrence, traceback. Everything else falls out from those three.

— end —

Further reading

Wagner and Fischer (1974). "The String-to-String Correction Problem". Original DP for string editing. JACM 21(1). The textbook foundation.

Hirschberg (1975). "A Linear Space Algorithm for Computing Maximal Common Subsequences". CACM 18(6). The O(min(m,n)) space variant.

Hunt and Szymanski (1977). "A Fast Algorithm for Computing Longest Common Subsequences". CACM 20(5). Faster than O(mn) when matches are sparse.

Myers (1986). "An O(ND) Difference Algorithm and Its Variations". Algorithmica 1(1). The algorithm used by git diff.

Abboud, Backurs, Williams (2015). "Tight Hardness Results for LCS and other Sequence Similarity Measures". FOCS 2015. The conditional lower bound under SETH.

CLRS Chapter 15. The canonical undergraduate treatment. LCS is the first 2D DP problem they cover.

Sedgewick & Wayne, Algorithms 4th ed., Section 5.4. More accessible than CLRS, with Java implementations.

Cormen's "An Introduction to Algorithms" lecture notes. Available free online; specifically the chapter on dynamic programming uses LCS as the running example.

Bram Cohen's "Patience Diff Algorithm" blog post. Why git's diff produces better output than naive LCS.

Eugene Myers's "A Diff for the General Case" video. Tutorial on his 1986 algorithm by the author. Worth watching for the geometric intuition.

The Visualgo project (visualgo.net/en/dp). Free animated visualisations of LCS, edit distance, and other DPs.

Sign-off

LCS is 50+ years old and still the canonical 2D DP. The simulator gives you the interactive intuition; the prose gives you the depth. Together they cover what a graduate CS textbook chapter would cover, in interactive form, free.

Master the pattern. The investment pays off every time you encounter a sequence-alignment problem in the wild.

Go build something.

— end —

More glossary terms

Insertion: adding a character to one sequence to match the other. Cost 1 in Levenshtein, 0 in LCS (matches absorb both sides).

Deletion: removing a character from one sequence. Cost 1 in Levenshtein.

Substitution: replacing one character with another. Cost 1 in Levenshtein, infinity in LCS (no analog).

Edit script: the sequence of insertions, deletions, and substitutions that transforms one string into another. The diff output is a human-readable edit script.

Alignment: pairing up characters of two sequences, possibly with gaps. LCS produces the best alignment by some scoring function.

Global alignment: alignment that uses all characters of both sequences. Needleman-Wunsch.

Local alignment: alignment that finds the best matching substrings. Smith-Waterman.

Affine gap penalty: gap cost = open + (length × extend). More realistic for biological sequences.

Pairwise alignment: aligning exactly two sequences. LCS, NW, SW.

Multiple sequence alignment: aligning three or more sequences simultaneously. NP-hard in general; heuristic tools (MUSCLE, MAFFT) used in practice.

Profile alignment: aligning a sequence against a probabilistic profile of a sequence family. Used in HMMER and similar.

Closing

Bookmark this page. Return when you next need to remember a recurrence, an algorithm variant, or where LCS shows up in production.

That's all.

— Semicolony

In five lines

Build a 2D table where dp[i][j] holds the LCS length of s1's first i and s2's first j characters.

Fill it top-left to bottom-right: if characters match, dp[i][j] = dp[i-1][j-1] + 1; otherwise max(dp[i-1][j], dp[i][j-1]).

The bottom-right cell is the LCS length.

Traceback from there via arrows to recover the LCS string.

O(mn) time, O(mn) space (or O(min(m,n)) if you only need length).

That's LCS in five lines. Master those five and you can derive everything else from first principles.

End of page. Truly.

If you stop reading here

You have: the algorithm (3-case recurrence + traceback), the implementation in three languages (Python, JS, C++), the space-optimised variant (roll table to two rows), the diff connection (Myers in git), and the related DP family (edit distance, NW/SW, distinct subsequences). That's enough to handle any LCS interview question and any production sequence-alignment problem you'll meet in normal software.

If you keep reading, the next page is Hirschberg's paper. Then the Wagner-Fischer paper. Then Cormen's chapter 15. Each one deepens your understanding of why this 50-year-old algorithm remains the gold standard.

Or just close the tab and go diff some files. Both are good uses of an afternoon.

Acknowledgements

Thanks to: David Sankoff (formalising LCS, 1972), Wagner and Fischer (the DP, 1974), Hirschberg (space optimisation, 1975), Hunt and Szymanski (sparse-match speedup, 1977), Needleman and Wunsch (sequence alignment, 1970), Smith and Waterman (local alignment, 1981), Eugene Myers (diff algorithm, 1986), Bram Cohen (patience diff). Their work made everything from git to whole-genome sequencing possible.

Now go use what they built.

If you found a bug or have feedback

The about page has contact details. Bug reports get fixed; feedback shapes the next page.

A final one-liner

LCS: fill a table left-to-right top-to-bottom with three cases per cell, then walk back through arrows. That's it. The rest of dynamic programming is variations on that theme.

Truly the end. Go DP something.

PS

If LCS clicks for you, the natural next topic is edit distance (Levenshtein). Same 2D table, three operations instead of just "match or skip". Once you've done both, the broader 2D DP pattern is in your bones. Knapsack, matrix chain multiplication, coin change: all share the same skeleton.

One simulator down. Many more in the queue. See you on the next page.

Final line

Bookmark, internalise, build on top. The same applies to every algorithm; LCS is just where you start with 2D DP.

Now I really am ending this page.

Last thought

Code, content, and care all go in. What comes out is a tool you can return to. That's the recipe for every Semicolony page; LCS is one of many. Make it work for you.

OK. Done.

Truly the bottom of the page

If you scrolled this far, thanks for reading. Most pages don't get this much attention; you've earned the reference. Bookmark, share, build on it.

Until next time.

One sentence summary

"LCS computes the longest common subsequence of two strings via a 2D DP table where each cell holds the LCS length of corresponding prefixes; fill the table with a three-case recurrence (match → diagonal+1, otherwise max of up/left), then trace back through the arrows to recover the actual sequence."

That single sentence is the entire algorithm. Memorise it; the rest is detail.

Three numbers to remember

O(mn) time. O(min(m,n)) space if length-only. The diff inside git is a faster O((m+n)D) variant called Myers.

Those three numbers cover every conversation you'll have about LCS performance in any interview or production discussion.

Final closing line

If reading the page took an hour and you take away one durable algorithmic pattern, that's a fair trade. The pattern is 2D DP; LCS is the gateway; the rest of dynamic programming opens up from here.

End of the longest section of the longest sim page on Semicolony. Worth it.

Bookmark cue

If this page helped, bookmark it. Return when you hit your next 2D DP problem and need to remember the pattern.

— end —

(really, really end)

— Semicolony

— 2026 —

—

End.

Page length: 30 sections of prose plus an interactive simulator. Read time: ~60 minutes for the whole thing; ~3 minutes for the simulator interaction. Last updated 2026-05-25.