Two on-call traces of the same checkout disagree on the retries in the middle. The edge pod logged ABCBDAB. Origin logged BDCABA. Product wants the longest sequence of event codes that appear in both traces, in the same order. A retry may sit between two shared codes — the shared sequence need not be a contiguous run. Two versions of a file, or two DNA reads, are the same job: keep order, allow holes.

The intern treats it as longest common substring: from every pair of starts, walk while the characters match, keep the longest run. That answers “longest adjacent overlap.” Kadane and sliding window already own contiguous on a scan. This job is allowed to skip.

LCS fills a grid: on a match take the diagonal plus one; otherwise skip — max of left or up. Walk the grid backward to emit one shared sequence.

This post is that grid and that walk. Families and the catalog live on the Algorithms Roadmap. A later sibling, LIS, asks for a longest increasing subsequence of one array — not this two-string table. Edit distance uses a related grid with costs; it is a different job. Neither is taught here.

The contiguous walk that answers substring

Nobody writes the double start-index loop because they love O(n²) character compares. They write it because the spec sounds like “what do these two strings share” and the first model is a run of adjacent matches.

static int longestCommonSubstring(String a, String b) {
    int best = 0;
    for (int i = 0; i < a.length(); i++) {
        for (int j = 0; j < b.length(); j++) {
            int k = 0;
            while (i + k < a.length() && j + k < b.length()
                    && a.charAt(i + k) == b.charAt(j + k)) {
                k++;
            }
            best = Math.max(best, k);
        }
    }
    return best;
}

On ABCBDAB and BDCABA that returns 2 (AB, BD, or BA). The shared story of the traces is length 4. The intern’s loop was not buggy. It solved substring.

The other wrong default is “enumerate every subsequence of A, test which appear in B.” That is O(2^{|A|} · |B|). It is the pairs-of-endpoints mistake from Kadane, moved onto subsets.

A subsequence may skip; a substring may not. If the spec forbids holes, you are not in this post.

The invariant: match, or skip one side

Let dp[i][j] be the LCS length of the first i characters of A and the first j of B. Empty prefixes are length 0, so row 0 and column 0 stay zero. For i > 0, j > 0:

  • If A.charAt(i - 1) == B.charAt(j - 1), this pair can extend the LCS of the two shorter prefixes: dp[i][j] = dp[i - 1][j - 1] + 1.
  • Else you cannot take both characters. Skip the last of A or the last of B: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]).

dp[i][j] = diagonal + 1 on a match, else max(up, left).

You never skip into a hole and count the hole. You skip a character by moving up or left, and you count a character only on a diagonal match. After the last cell, dp[m][n] is the length. One LCS is recovered by walking from that cell back to (0, 0).

Note: Seed the borders with 0. If you seed the first row with 0, 1, 2, … you are filling a cost table (how many deletes to empty a prefix). That is the edit-distance grid, later in the series — a different job, not a clever LCS initializer.

A walk: two traces, length 4

Classic pair. Length 4. One LCS is BCBA. BDAB and BCAB are others; the backtrace below picks one.

A = ABCBDAB
B = BDCABA

dp (rows = prefixes of A, cols = prefixes of B):

        ''  B  D  C  A  B  A
   ''    0  0  0  0  0  0  0
   A     0  0  0  0  1  1  1
   B     0  1  1  1  1  2  2
   C     0  1  1  2  2  2  2
   B     0  1  1  2  2  3  3
   D     0  1  2  2  2  3  3
   A     0  1  2  2  3  3  4
   B     0  1  2  2  3  4  4

length = dp[7][6] = 4

match at (A vs A): the last A of A against the last A of B
  diagonal from 3 → 4

backtrace (on a mismatch, prefer up when up >= left):
  (B,A) skip up → (A,A) match A
  → (D,B) skip up → (B,B) match B
  → (C,A) skip left → (C,C) match C
  → (B,D) skip left → (B,B) match B
  reverse the taken letters → BCBA

The first B of A matches the first B of B (diagonal 0 → 1). The Cs match. The second B of A matches the second B of B. The last A of A matches the last A of B. The extra A, D, and trailing B on A, and the extra D on B, were skips. Order of the taken letters is the order they appeared — that is the subsequence contract.

Empty A or empty B: the table is all zeros, LCS is "". Identical strings: the string itself, every step a match. No character in common: every cell takes max of left/up, stays 0.

Java: fill the grid, then walk it backward

There is no String.lcs. The JDK map on the roadmap lists sorts, binary search, and searches. This job is a table you write.

Length only, matching the walk:

static int lcsLength(String a, String b) {
    int m = a.length();
    int n = b.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a.charAt(i - 1) == b.charAt(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]);
            }
        }
    }
    return dp[m][n];
}

The caller usually wants the sequence, not only 4. Keep the table and walk from (m, n). On a match, take that character and go diagonal. On a mismatch, step into the neighbor that holds the same length as the current cell — prefer up on a tie so the walk is deterministic.

static String lcs(String a, String b) {
    int m = a.length();
    int n = b.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a.charAt(i - 1) == b.charAt(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]);
            }
        }
    }
    StringBuilder sb = new StringBuilder();
    int i = m;
    int j = n;
    while (i > 0 && j > 0) {
        if (a.charAt(i - 1) == b.charAt(j - 1)) {
            sb.append(a.charAt(i - 1));
            i--;
            j--;
        } else if (dp[i - 1][j] >= dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    return sb.reverse().toString();
}

On the walk, that returns BCBA. Flip the >= to a strict > and you may emit a different LCS of the same length (BDAB is in the set). Both are correct. One backtrace does not list every LCS; the number of them can be exponential.

Note: The table is 1-based prefixes; charAt is 0-based. Off-by-one here looks like a missing first or last letter, not a crash. Events that are words, not single codes, use the same recurrence on token arrays — compare a[i - 1].equals(b[j - 1]) instead of charAt.

Length-only can keep two rows of size n + 1 (or m + 1 if that is shorter) and swap each i. That is O(min(m, n)) extra memory. You cannot reconstruct from two rows without extra bookkeeping; if you need the string, keep the full table or recompute.

Complexity

WhatCostWhy
TimeO(mn)One cell per prefix pair; match/skip is O(1)
Extra space (sequence)O(mn)The int[][] you walk backward
Extra space (length only)O(min(m, n))Two rolling rows
Substring nested walkO(mn · L)Every start pair, then a run of length L
Subsequence enumO(2^m · n)Every subset of A, tested in B
OutputO(k)One LCS of length k = dp[m][n]

The two input strings are whoever owns them. LCS does not get cheaper because the strings are “almost equal”; every cell is still filled. Quadratic in the two lengths, one sequence from one backtrace. A correct 2^m enumerator is still the wrong default on traces.

When not to use LCS

Skip this grid when the job is not “longest shared subsequence of two sequences.”

  • You needed a contiguous shared run. That is longest common substring (the intern’s loop, or a DP that resets to 0 on mismatch). Finding a known contiguous pattern in one text is KMP, not LCS. Kadane and sliding window remain the contiguous tools on a numeric scan — do not import this table to replace them.
  • You needed insert / delete / substitute costs. Same family of grid, different recurrence. Edit distance is a costed table later in the series (/posts/algorithms/algo-edit-distance/, after LIS). Do not seed LCS borders with i and j and call it a shortcut.
  • You needed a longest increasing subsequence of one array. That is LIS, the next post — n log n is available; this m × n table is the wrong shape. Do not turn one array into “LCS against its sorted unique copy” and call it the LIS article.
  • You needed every LCS. One backtrace emits one. Enumerating all is a different search; the count can explode. If the spec wants any witness of the length, the walk above is enough.
  • The strings are huge and you only needed the length. Keep two rows. If you also needed the string and mn ints do not fit, that is a different reconstruction (Hirschberg and friends). Out of scope here — as are contest-only DP variants (digit DP, SOS). Cardinality and frequency sketches live on HyperLogLog and Count-Min Sketch, not this table.
  • You needed a line-oriented diff as a product. diff / Myers is a related question with a different bill. LCS of two token lists is the textbook core, not git diff.

Two sequences, order kept, holes allowed, one witness — that is the job. Anything else is a different procedure that may look like a grid.

Cheat sheet

Job:         longest common subsequence of two strings (not substring)
Cell:        dp[i][j] = LCS length of A[0..i) and B[0..j)
Match:       dp[i][j] = dp[i-1][j-1] + 1
Skip:        dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Borders:     row 0 and col 0 are 0 (empty prefix)
Reconstruct: from (m,n); match → take char, diagonal; else step to max neighbor
Ties:        pick a side; you get one LCS, not every LCS
Empty:       "" / length 0
Time/space:  O(mn) / O(mn) for the string; two rows if length only
JDK:         none — write the table
Not this:    substring, Kadane/window, LIS, edit-distance costs, all-LCS dump

Do:

  • Name subsequence vs substring before you allocate dp.
  • Index the table as prefixes (i, j from 1) and read charAt(i - 1).
  • Reconstruct from the same table if the caller needs the codes, not only the length.
  • Tokenize first when the “characters” are log events or lines.

Don’t:

  • Walk every adjacent run and report it as LCS.
  • Seed borders with 0, 1, 2, … and claim the cells are lengths.
  • Quote Kadane’s O(n) for a two-string grid.
  • Enumerate 2^m subsequences once m is a trace, not a toy.

Wrap-up

LCS replaces “every shared subset” and “every contiguous overlap” with one decision per prefix pair: take a matching pair on the diagonal, or skip a character on one side. The last cell is the length. One walk backward is one shared sequence. Empty input is the empty string, not a throw. Several LCS of that length may exist; one backtrace is a witness, not a catalog.

The layout is two sequences. The procedure is this table. When the job is contiguous, increasing-in-one-array, or a costed edit script, this grid is the wrong named procedure — start from the Algorithms Roadmap and pick the job again.

Next optional step in the series Longest increasing subsequence in n log n, not only the quadratic table. LIS: Longest Increasing Subsequence in n log n