Foundations — DP problems — Longest Common Subsequence (LCS)

This page assumes you have seen nothing. We build every letter, arrow, and bracket the parent LCS note leans on, one brick at a time. If a term below already feels obvious, skim — but each one is a place beginners silently trip.

1. What a "string" is

The picture: think of beads on a straight wire. Each bead is a character, and the wire fixes their order — you cannot slide bead 4 in front of bead 2 without cutting the wire.

Why the topic needs it. LCS compares two such wires and asks which beads line up in both, keeping the wire order intact. Without a fixed order there would be no "same relative order" to protect.

2. Naming the strings and their characters: $X$, $Y$, $x_i$, $y_j$

The parent writes $X=x_1{x}_2\dots x_m$ and $Y=y_1{y}_2\dots y_n$. Let's earn every piece.

The picture: two rows of beads stacked. A finger labelled $i$ points at one bead in the top row $X$; a finger labelled $j$ points at one bead in the bottom row $Y$.

3. Subsequence vs substring — the picture that separates them

This is THE distinction the whole topic rides on.

The picture — same string, two different rules:

From ABCDE:

• ACE is a subsequence (keep A, skip B, keep C, skip D, keep E — order preserved, gaps allowed).
• ACE is not a substring (A, C, E are not next to each other).
• BCD is a substring (a solid slice).

Why the topic needs it. LCS = longest subsequence common to both strings. Confusing it with substring gives a completely different recurrence (see the parent's mistake box). Nail this now and half the traps vanish. The contiguous cousin lives in Longest Common Substring.

4. Prefix — the chunks we actually recurse on

The picture: a sliding cut. Put a knife after position $i$; everything to the left of the knife is the prefix $X[\mathrm{1..}i]$. Slide the knife right and the prefix grows.

5. The label $L(i,j)$ — a function of two pointers

Why "length" and not the string itself? Lengths are single numbers, trivial to compare and add. We compute all lengths first (fast), then walk backwards to recover an actual string only if we want one (the parent's traceback). Separating "how long" from "which letters" keeps the core simple.

The final answer we want is $L(m,n)$ — the box with both dials turned all the way up, i.e. both full strings.

6. The tools inside the recurrence: $\max$, $+1$, and the two cases

The parent's formula uses two operations. Both deserve a plain-words picture.

Here $\ne$ means "not equal to". The symbol $=$ inside a case is a test ("are these two characters the same?"), not an assignment.

7. The base case and why the grid has an extra row/column

The picture: an empty wire has no beads; no bead can match against nothing. So every cell in row $0$ or column $0$ of the grid is $0$ — these are the walls we build outward from.

8. Reading the grid: up, left, diagonal

Every filled cell $L(i,j)$ is decided by three neighbours already computed:

The picture: stand on a cell. The match rule reaches to the diagonal (both dials down). The mismatch rule reaches up and left and keeps the bigger. This directional habit — "match goes diagonal, miss takes the max" — is the entire mechanical skill.

Prerequisite map

Equipment checklist

Cover the right side and test yourself. If any answer is fuzzy, reread that section before tackling the parent's derivation.