How does the longest-common-subsequence recurrence really differ from edit distance, beyond max versus min?

## The claim under test "LCS and edit distance are the same table with different labels" is the confident-sounding wrong answer this question exists to catch. The tables have the same *shape* — `(m+1)` by `(n+1)`, indexed by prefix lengths, filled row-major, each cell reading up, left and up-left. What differs is the move set, and the difference is not cosmetic. ## Side by side Let `a` and `b` be the two inputs, and let both tables be indexed by prefix lengths. **Longest common subsequence** — maximize the number of characters kept in order: - `dp[0][j] = 0`, `dp[i][0] = 0` (no common characters with an empty prefix) - match (`a[i-1] == b[j-1]`): `dp[i][j] = dp[i-1][j-1] + 1` - mismatch: `dp[i][j] = max(dp[i-1][j], dp[i][j-1])` **Edit distance** — minimize the number of operations: - `dp[0][j] = j`, `dp[i][0] = i` - match: `dp[i][j] = dp[i-1][j-1]` - mismatch: `dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])` ## The structural difference: three moves versus two The mismatch branch of the distance table has **three** options; the subsequence table has **two**. The missing one is the diagonal, and the diagonal on a mismatch has a specific meaning: *substitution* — pay one, and consume a character from both strings at once. A subsequence has no such operation. Its whole job is to choose characters that literally agree, so pairing two unequal symbols is not merely expensive, it is not a legal move. That is why the subsequence recurrence can only advance one side at a time on a mismatch. The direction of optimization follows from that, rather than being the real difference: keeping characters is good, so you take a max; spending operations is bad, so you take a min. Someone who has only memorized "one is max, one is min" will get the mismatch branch wrong under pressure and quietly import a diagonal term that inflates every subsequence length. ## Where they do coincide, exactly Remove substitution from the operation set — allow only insertions and deletions, which is what a line-oriented diff does when it reports a changed line as one removal plus one addition — and the two problems become the same problem. The minimum number of insertions and deletions is `indel(a, b) = m + n - 2 * LCS(a, b)` because every character not in the common subsequence must be deleted from `a` or inserted into `b`. Equivalently, pricing a substitution at 2 makes it never worth using, since a delete plus an insert already costs 2 and is strictly more flexible. This identity is the honest version of "they're related": they are two readings of the same alignment when substitution is off the table, and genuinely different optimizations when it is on. ## Consequences you can name - **Similarity versus cost.** A subsequence length is a similarity score that grows with agreement and is not a metric; a distance is a cost that shrinks with agreement and — with symmetric unit costs — satisfies the triangle inequality. Normalizing a subsequence length by `max(m,n)` gives a ratio; a distance is already comparable across pairs only if you account for length, since `distance >= |m - n|` always. - **What the answer cell holds.** Bottom-right in both cases, but one is a length and one is a count of operations, and they are not interchangeable inputs to a threshold. - **Cost.** Both are `O(m*n)` time in the plain table form, and both can be reduced to one row of space if you only want the number. ## What a good answer sounds like "Same shape, different move set. On a mismatch the distance table can still go diagonal — that's a substitution — and the subsequence table can't, because unequal characters can never pair. Base rows differ: zeros versus counting up. And if you ban substitution or price it at 2, the insert-delete distance is exactly `m + n - 2*LCS`, which is the precise sense in which they're the same problem."