DP problems — Longest Common Subsequence (LCS): Worked examples

Before anything, one reminder of the machine we are running (from the parent). We write $X = x_{1} x_{2} \dots x_{m}$ and $Y = y_{1} y_{2} \dots y_{n}$ , and $L (i, j)$ is the LCS length of the first $i$ letters of $X$ and the first $j$ letters of $Y$ .

The scenario matrix

Every LCS problem falls into one of these cells. The examples below are labelled with the cell they hit, and together they cover all of them.

#	Cell (case class)	What makes it special	Example
C1	Typical overlap	Both strings non-empty, partial match with gaps	Ex. 1
C2	Zero input (empty string)	One string is `""`	Ex. 2
C3	No common characters	Disjoint alphabets → answer 0	Ex. 3
C4	Identical strings	Upper bound: LCS = whole string	Ex. 4
C5	One is a subsequence of the other	LCS = the shorter one entirely	Ex. 5
C6	Ties / multiple valid LCS	Traceback branches, several answers	Ex. 6
C7	Repeated characters trap	Same letter appears many times — order still rules	Ex. 7
C8	Real-world word problem	Two playlists / DNA / diff	Ex. 8
C9	Exam twist	LCS vs substring on the same input	Ex. 9

Recall Why these nine and not more?

The recurrence has exactly three branches (base, match, mismatch). "Every scenario" means exercising each branch under every degenerate condition: empty input hits only the base row (C2), disjoint input hits only mismatch (C3), identical input hits only match (C4). The rest are combinations. There is no fourth kind of behaviour to worry about. Any LCS input reduces to one of these ::: yes — base, all-match, all-miss, or a mixture; the matrix covers each.

Example 1 — Typical overlap (cell C1)

Worked example

ABCBDAB vs BDCAB Find the LCS length.

Forecast: eyeball it — which letters can you keep in order from both? Write your guess (I predict a small number, 3 or 4) before reading.

Step 1 — set up the table. $X =$ ABCBDAB ( $m = 7$ ), $Y =$ BDCAB ( $n = 5$ ). Build an $(8) \times (6)$ grid whose row 0 and column 0 are all zeros. Why this step? The extra zero border encodes the base case $L (0, j) = L (i, 0) = 0$ : comparing against an empty prefix yields nothing. Look at the grey border in the figure.

Step 2 — fill row by row using "match→diagonal+1, miss→max". Each cell only ever peeks at three neighbours: up-left (diagonal), up, left. Why this step? Those are the only smaller subproblems the recurrence references. The green cells in the figure are matches (diagonal + 1); the plain cells inherited $max (up, left)$ .

Step 3 — read the corner. The bottom-right cell holds $L (7, 5) = 4$ . Why this step? $L (m, n)$ is by definition the LCS of the full strings.

Answer: length 4 (e.g. BCAB or BDAB).

Verify: BCAB appears in AB C BDAB and in BDCAB → B D C A B, both in order. ✅ Length matches the corner. Length can never exceed $min (m, n) = 5$ , and 4 ≤ 5 — sane.

Example 2 — Zero input, an empty string (cell C2)

Example 3 — No common characters (cell C3)

Example 4 — Identical strings (cell C4)

Example 5 — One string is a subsequence of the other (cell C5)

Example 6 — Ties and multiple valid answers (cell C6)

Worked example

ABCBDAB vs BDCAB — recover a string Same numbers as Ex. 1, but now trace back the actual LCS and notice it isn't unique.

Forecast: if two neighbours (up and left) are equal, which do we follow? Does the choice matter for the length?

Step 1 — start at the corner $L (7, 5) = 4$ and walk backwards. Why this step? The corner is the answer; traceback asks "which neighbour built me?"

Step 2 — on a match, go diagonal and record the letter. When $x_{i} = y_{j}$ , this cell was $1 + diagonal$ , so that shared letter belongs to the LCS. Why this step? The value literally came from the diagonal $+ 1$ ; following it recovers the character responsible.

Step 3 — on a mismatch, step toward the larger of up/left; on a tie, either works. A tie means two different subsequences of equal length exist. Why this step? Both parents carry the same optimal value, so both lead to a valid (equally long) LCS — the length is identical, only the string differs.

Answer: length 4; two valid strings are BCAB (red path) and BDAB (blue path).

Verify: BCAB and BDAB are both length 4 and both appear in order in both inputs (BDCAB contains B D C A B → pick B_CAB and BD_AB). Ties never change the length, only the witness. ✅

Example 7 — Repeated characters trap (cell C7)

Example 8 — Real-world word problem (cell C8)

Worked example Two friends' cartoon playlists

Aki watched, in order: Tom Jerry Doraemon Shinchan Pokemon. Bina watched, in order: Jerry Shinchan Pokemon Tom. What is the longest playlist of cartoons both watched in the same order (skips allowed, no reshuffling)?

Forecast: they clearly share several titles, but order constrains you. Guess the length.

Step 1 — treat each cartoon as one "letter". Encode $X =$ [Tom, Jerry, Doraemon, Shinchan, Pokemon], $Y =$ [Jerry, Shinchan, Pokemon, Tom]. Why this step? LCS doesn't care that "letters" are whole words — it compares tokens for equality and order. This is exactly how a diff tool treats lines of a file.

Step 2 — run the recurrence on tokens. Matches occur at Jerry, Shinchan, Pokemon, Tom. But Tom is first in Aki's list and last in Bina's — using it would break order after Pokemon. Why this step? Order is the whole point; the DP automatically refuses out-of-order matches by only ever moving up/left/diagonal.

Step 3 — the longest in-order chain is Jerry → Shinchan → Pokemon. Why this step? These three appear in that order in both lists; Tom can't be appended in order for both, so it's dropped.

Answer: length 3 — the shared in-order playlist is Jerry, Shinchan, Pokemon.

Verify: in Aki's list Jerry(2) < Shinchan(4) < Pokemon(5) ✅ increasing; in Bina's list Jerry(1) < Shinchan(2) < Pokemon(3) ✅ increasing. Adding Tom fails order in one list, so 3 is maximal. This is precisely diff on lines. ✅

Example 9 — Exam twist: LCS vs Substring on the same input (cell C9)

Worked example

ABCBDAB vs BDCAB — give BOTH answers Report the Longest Common Subsequence length AND the Longest Common Substring length, and explain the gap.

Forecast: substring must be contiguous; subsequence may skip. Which is bigger, and by how much?

Step 1 — LCS (subsequence). From Ex. 1, gaps allowed → length 4 (BCAB). Why this step? The mismatch branch keeps $max (up, left)$ , so progress survives a mismatch — that's what lets us jump gaps.

Step 2 — LCSubstring uses a different recurrence. For substrings, a mismatch resets to 0, and the answer is the maximum over all cells, not the corner:

S (i, j) = {1 + S (i - 1, j - 1) 0 x_{i} = y_{j} x_{i} \neq = y_{j}, answer = i, j max S (i, j) .

Why this step? Contiguity means one mismatch breaks the run entirely; you can't inherit from up/left.

Step 3 — find the longest contiguous run common to both. The pieces AB (in ...DABof X andBDC**AB**`` of Y) and CB don't extend; the best contiguous block is length **2** (AB). *Why this step?* No 3-letter contiguous chunk of ABCBDABalso appears contiguously inBDCAB`.

Answer: LCS = 4 (BCAB); Longest Common Substring = 2 (AB). See Longest Common Substring.

Verify: substring ≤ subsequence always (a contiguous common block is also a common subsequence), and $2 \leq 4$ ✅. The gap is the "reset vs inherit" difference between the two recurrences.

Coverage recap

Recall Did we hit every cell?

C1 Ex.1 · C2 Ex.2 · C3 Ex.3 · C4 Ex.4 · C5 Ex.5 · C6 Ex.6 · C7 Ex.7 · C8 Ex.8 · C9 Ex.9. Every branch of the recurrence exercised under every degenerate condition. The tightest general bounds on any LCS length ::: $0 \leq L (m, n) \leq min (m, n)$ — hit 0 in C3, hit $min$ in C4/C5/C7. Which cell shows LCS and substring diverging ::: C9 (Ex. 9): 4 vs 2.

Active recall

LCS of ABCBDAB and BDCAB?

length 4 (BCAB or BDAB).

LCS of any string with ""?

0 — the base-case border alone.

LCS of two strings with disjoint alphabets?

0 — no match branch ever fires.

LCS of a string with itself (length

k

k

— the whole string; upper bound

min (m, n)

LCS of AAAA and AA?

2 — bottleneck is the shorter supply of As.

Longest Common Substring of ABCBDAB and BDCAB?

2 (AB); substring resets to 0 on mismatch.

General bounds on LCS length?

0 \leq L (m, n) \leq min (m, n)

Why do ties give multiple LCS but same length?

equal up/left neighbours are two optimal parents; both length-optimal, different witness strings.

Connections

Parent topic — the recurrence these examples exercise.
Dynamic Programming — the table-filling paradigm behind every example.
Longest Common Substring — the contiguous variant contrasted in Ex. 9.
Edit Distance — same grid, different cell rule; a natural next stress test.
Longest Increasing Subsequence — reduces to LCS; the token-LCS trick of Ex. 8 reappears.
Diff Algorithm — Ex. 8 is a line-level diff.
Sequence Alignment — the DNA generalisation of Ex. 8.