--- title: "Longest Common Subsequence" description: "2D DP table over two strings" source: https://vizlearn.app/algorithms/dp/longest-common-subsequence access: premium (interactive player requires Lifetime; this doc is free) --- # Longest Common Subsequence Longest common subsequence (LCS) models the alignment problem behind a code diff: find the longest sequence that appears in two versions in the same order, while allowing insertions and deletions between matches. The shared sequence becomes the stable backbone; everything outside it is material one version added, removed, or moved around. Think of two people remembering the same trip. Their stories contain different details, but several events still occur in the same order. LCS keeps the longest ordered backbone shared by both accounts. It may skip details in either story; it never rearranges the events it keeps. ## How longest common subsequence works The brute-force idea is brutally literal. If string `a` has length `m`, it has `2^m` subsequences, including the empty one. You could generate every candidate and test whether it appears in `b`, but that bill becomes ridiculous before the strings become interesting. Dynamic programming avoids repeating the same prefix comparisons. Let `dp[i][j]` mean the LCS length of `a[:i]` and `b[:j]`. The extra row and column represent empty prefixes, so every cell in row 0 or column 0 is 0. Each remaining cell looks at the trailing characters of its two prefixes. If `a[i - 1]` equals `b[j - 1]`, that shared character extends a solution that excludes both trailing positions: `dp[i][j] = dp[i - 1][j - 1] + 1`. The diagonal matters. Reading top or left and adding 1 could reuse one of the current positions and overcount. If the characters differ, they contribute no new shared character. The algorithm drops one trailing position or the other and keeps the better result: `dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])`. A tie means both shortened prefix pairs preserve the same optimal length. Return to the trip analogy: two versions of the shared memory are equally long, so either route can still be honest. This implementation prefers up only to make playback and output deterministic. The rule chooses one optimal sequence; it does not make that sequence unique. The lower-right cell gives the optimal length. To recover the letters, start there and trace backward. A character match moves diagonally and emits that character. A mismatch moves toward a neighbor that preserves the current length. ## Why greedy matching returns a shorter answer Earliest-match greedy sounds reasonable: scan `a` from left to right, and match each character to the earliest still-available copy in `b`. Its first decision on the default input is the trap. For `a = ABCBDAB` and `b = BDCABA`, greedy sees `a[0] = A` and takes the earliest `A` in `b`, at `b[3]`. That commitment advances its cursor past `b[0..2] = B, D, C`. Those positions are gone for good, including the `B` and `C` that a longer answer needs. Greedy then takes `B` at `b[4]` and `A` at `b[5]`, producing `ABA`, length 3. Dynamic programming refuses to make that first commitment. It preserves the alternatives represented by top and left prefix states. The finished table recovers `BCBA`, using `B` at `b[0]`, `C` at `b[2]`, `B` at `b[4]`, and `A` at `b[5]`, for length 4. The contrast is not that greedy chose an invalid subsequence. `ABA` is valid. It is simply shorter because a locally early match destroyed a globally better route. ## Longest common subsequence step by step The default run compares `ABCBDAB` with `BDCABA`. 1. The greedy prelude takes `A` at `a[0]` and matches it to `b[3]`. The crossed-out `B`, `D`, and `C` show the cost immediately: after this match, greedy cannot revisit them. 2. Greedy continues from the right of `b[3]`, matches `B` at `a[1]` to `b[4]`, then matches `A` at `a[5]` to `b[5]`. It stops with `ABA`, length 3. The animation leaves this result visible as the baseline to beat. 3. DP initializes row 0 and column 0 to zero. These cells answer every comparison involving an empty prefix. 4. The table fills left to right, one row at a time. The first three cells compare `A` with `B`, `D`, and `C`; both candidates are 0, so each cell simply writes 0. No traceback terminology is needed yet. At `dp[1][4]`, `A` matches `A`, so diagonal 0 becomes 1. At `dp[2][1]`, `B` matches `B` and also writes 1. 5. Later cells carry real alternatives. A mismatch copies the larger of top and left. At `dp[3][5]`, both neighbors equal 2, so either direction preserves an optimal prefix. The lesson records up as its deterministic tie choice. 6. When the final cell is filled, `dp[7][6] = 4` lights up beside four empty result slots. The length is known, but the letters are not. That is the reason traceback exists. 7. Traceback starts at `(7, 6)`. `B` and `A` differ, and the top neighbor preserves 4, so the cursor moves to `(6, 6)`. There `A` matches `A`; the animation places `A` in the rightmost result slot and moves diagonally to `(5, 5)`. 8. From `(5, 5)`, the cursor moves up to `(4, 5)`, where `B` matches `B`. It then moves left from `(3, 4)` to `(3, 3)`, where `C` matches `C`. 9. One more left move reaches `(2, 1)`. `B` matches `B`, filling the first slot. Reading the slots left to right gives `BCBA`, length 4. `BCBA` is one optimal answer. Another legal tie rule can recover `BDAB`, also length 4. The table proves the length; the chosen traceback path identifies one witness. ## Time and space complexity | Measure | Cost | | -------------------------- | ---------: | | Naive enumeration from `a` | O(2^m × n) | | DP table construction | O(m × n) | | Full table space | O(m × n) | | Traceback | O(m + n) | Here `m` and `n` are the two string lengths. The naive bound assumes each generated subsequence of `a` is checked against `b` in O(n) time. If you need only the length, compress the DP table to two rows, or one carefully updated row, for O(min(m, n)) space. Reconstruction needs more information, so this animation keeps the full table. ## Edge cases - If either string is empty, the answer is the empty sequence with length 0. - If the strings share no characters, every non-base cell stays 0 and traceback emits nothing. - Repeated characters can create several optimal paths. A fixed tie rule makes one result repeatable, not uniquely correct. - Identical strings have the whole string as their LCS. - LCS is a subsequence problem, not a substring problem. Selected characters may have gaps between them. ## Common mistakes - Using `max(top, left) + 1` when characters match. A match extends the diagonal state. - Adding 1 on a mismatch. Different trailing characters have contributed no shared character. - Treating an early zero tie as a profound path decision. Both candidates are 0; write 0 and keep moving. - Forgetting the empty-prefix row and column, which forces special cases into every boundary cell. - Filling a cell before its top, left, and diagonal dependencies are ready. - Assuming earliest matches are safe. On the default input, matching `A` at `a[0]` to `b[3]` burns the prefix that supports `BCBA`. - Calling the recovered letters unique. The optimal length is fixed, but several LCS strings may realize it.