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

3.7.10 · D3 · Coding › Algorithm Paradigms › DP problems — Longest Common Subsequence (LCS)

Shuru karne se pehle, ek reminder us machine ka jo hum use kar rahe hain (parent se). Hum likhte hain $X = x_{1} x_{2} \dots x_{m}$ aur $Y = y_{1} y_{2} \dots y_{n}$ , aur $L (i, j)$ hai LCS length $X$ ke pehle $i$ letters aur $Y$ ke pehle $j$ letters ki.

Scenario matrix

Har LCS problem in cells mein se kisi ek mein aati hai. Neeche ke examples us cell ke saath label kiye hain jisme woh fit hote hain, aur milke yeh sab ko cover karte hain.

#	Cell (case class)	Kya special hai	Example
C1	Typical overlap	Dono strings non-empty, partial match with gaps	Ex. 1
C2	Zero input (empty string)	Ek string `""` hai	Ex. 2
C3	No common characters	Disjoint alphabets → answer 0	Ex. 3
C4	Identical strings	Upper bound: LCS = poori string	Ex. 4
C5	Ek doosre ki subsequence hai	LCS = poori choti wali	Ex. 5
C6	Ties / multiple valid LCS	Traceback branches, kai answers	Ex. 6
C7	Repeated characters trap	Same letter kai baar aata hai — order phir bhi rule karta hai	Ex. 7
C8	Real-world word problem	Do playlists / DNA / diff	Ex. 8
C9	Exam twist	LCS vs substring same input par	Ex. 9

Recall Yeh nau hi kyun, zyada kyun nahi?

Recurrence mein exactly teen branches hain (base, match, mismatch). "Har scenario" ka matlab hai har degenerate condition mein har branch ko exercise karna: empty input sirf base row hit karta hai (C2), disjoint input sirf mismatch hit karta hai (C3), identical input sirf match hit karta hai (C4). Baaki combinations hain. Worry karne ke liye koi chautha behavior nahi hai. Koi bhi LCS input in mein se kisi ek tak reduce hota hai ::: haan — base, all-match, all-miss, ya mixture; matrix har ek ko cover karta hai.

Example 1 — Typical overlap (cell C1)

Worked example

ABCBDAB vs BDCAB LCS length nikalo.

Forecast: eyeball karo — dono se order mein kaunse letters rakh sakte ho? Apna guess likho (main predict karta hoon ek chota number, 3 ya 4) padhne se pehle.

Step 1 — table set up karo. $X =$ ABCBDAB ( $m = 7$ ), $Y =$ BDCAB ( $n = 5$ ). Ek $(8) \times (6)$ grid banao jiska row 0 aur column 0 sab zeros hain. Yeh step kyun? Extra zero border base case $L (0, j) = L (i, 0) = 0$ encode karta hai: empty prefix se compare karne par kuch nahi milta. Figure mein grey border dekho.

Step 2 — row by row "match→diagonal+1, miss→max" se fill karo. Har cell sirf teen neighbours dekhti hai: up-left (diagonal), up, left. Yeh step kyun? Woh sirf wahi chote subproblems hain jo recurrence reference karta hai. Figure mein green cells matches hain (diagonal + 1); plain cells ne $max (up, left)$ inherit kiya.

Step 3 — corner padho. Bottom-right cell mein $L (7, 5) = 4$ hai. Yeh step kyun? $L (m, n)$ by definition poori strings ka LCS hai.

Answer: length 4 (jaise BCAB ya BDAB).

Verify: BCAB AB C BDAB mein aur BDCAB mein milta hai → B D C A B, dono order mein. ✅ Length corner se match karti hai. Length kabhi $min (m, n) = 5$ se zyada nahi ho sakti, aur 4 ≤ 5 — sane hai.

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

Example 3 — No common characters (cell C3)

Example 4 — Identical strings (cell C4)

Worked example

MATCH vs MATCH LCS nikalo.

Forecast: agar strings same hain, toh sabse badi shared subsequence kya ho sakti hai?

Step 1 — diagonal sab matches hai. Main diagonal par position-by-position compare karo: $x_{1} = y_{1}$ , $x_{2} = y_{2}$ , … har pair match karta hai. Yeh step kyun? Equal strings ka matlab hai $x_{k} = y_{k}$ sab $k$ ke liye, toh match branch poore diagonal par fire karta hai, har fire $+ 1$ add karta hai.

Step 2 — additions count karo. Paanch matches → paanch $+ 1$ s → $L (5, 5) = 5$ . Yeh step kyun? Diagonal walk $L (k, k) = 1 + L (k - 1, k - 1)$ telescope karta hai: $L (5, 5) = 5$ .

Answer: length 5, LCS = MATCH khud.

Verify: LCS length kabhi $min (m, n) = 5$ se zyada nahi ho sakti; yahan hum exactly woh ceiling hit karte hain, jaise identical strings ko karna hi chahiye. ✅ Yeh upper bound hai: LCS = length jab $X = Y$ ho.

Example 5 — Ek string doosri ki subsequence hai (cell C5)

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

Worked example

ABCBDAB vs BDCAB — ek string recover karo Ex. 1 ke same numbers, lekin ab actual LCS trace back karo aur notice karo yeh unique nahi hai.

Forecast: agar do neighbours (up aur left) equal hain, toh kaunsa follow karte hain? Kya choice length ke liye matter karti hai?

Step 1 — corner se start karo $L (7, 5) = 4$ aur backwards chalo. Yeh step kyun? Corner answer hai; traceback poochta hai "kaunse neighbour ne mujhe banaya?"

Step 2 — match par, diagonal jao aur letter record karo. Jab $x_{i} = y_{j}$ , yeh cell $1 + diagonal$ thi, toh woh shared letter LCS ka hissa hai. Yeh step kyun? Value literally diagonal $+ 1$ se aayi; usse follow karne par woh character milta hai jo responsible tha.

Step 3 — mismatch par, up/left mein se bade ki taraf jao; tie par, dono kaam karte hain. Tie ka matlab do different equal-length subsequences exist karti hain. Yeh step kyun? Dono parents same optimal value carry karte hain, toh dono valid (equally long) LCS tak le jaate hain — length identical hai, sirf string alag hoti hai.

Answer: length 4; do valid strings hain BCAB (red path) aur BDAB (blue path).

Verify: BCAB aur BDAB dono length 4 hain aur dono dono inputs mein order mein milti hain (BDCAB mein B D C A B → B_CAB aur BD_AB pick karo). Ties kabhi length nahi badlate, sirf witness badlata hai. ✅

Example 7 — Repeated characters trap (cell C7)

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

Worked example Do doston ki cartoon playlists

Aki ne, order mein, dekha: Tom Jerry Doraemon Shinchan Pokemon. Bina ne, order mein, dekha: Jerry Shinchan Pokemon Tom. Woh sabse lamba playlist kaunsa hai jisme dono ne same order mein cartoons dekhe (skips allowed, reshuffling nahi)?

Forecast: clearly kuch titles share hain, lekin order constraint karta hai. Length guess karo.

Step 1 — har cartoon ko ek "letter" samjho. Encode karo $X =$ [Tom, Jerry, Doraemon, Shinchan, Pokemon], $Y =$ [Jerry, Shinchan, Pokemon, Tom]. Yeh step kyun? LCS ko parwah nahi ki "letters" poore words hain — woh tokens ko equality aur order ke liye compare karta hai. Ek diff tool bilkul aise hi kisi file ki lines treat karta hai.

Step 2 — tokens par recurrence chalao. Matches hote hain Jerry, Shinchan, Pokemon, Tom par. Lekin Tom Aki ki list mein pehle hai aur Bina ki list mein aakhir mein — isko use karna Pokemon ke baad order tod dega. Yeh step kyun? Order hi poora point hai; DP automatically out-of-order matches refuse karta hai kyunki woh sirf up/left/diagonal move karta hai.

Step 3 — sabse lamba in-order chain hai Jerry → Shinchan → Pokemon. Yeh step kyun? Yeh teen dono lists mein us order mein milte hain; Tom dono ke liye order mein append nahi ho sakta, toh drop ho jaata hai.

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

Verify: Aki ki list mein Jerry(2) < Shinchan(4) < Pokemon(5) ✅ increasing; Bina ki list mein Jerry(1) < Shinchan(2) < Pokemon(3) ✅ increasing. Tom add karna ek list mein order fail karta hai, toh 3 maximal hai. Yeh exactly diff lines par hai. ✅

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

Worked example

ABCBDAB vs BDCAB — DONO answers do Longest Common Subsequence length AUR Longest Common Substring length report karo, aur gap explain karo.

Forecast: substring contiguous honi chahiye; subsequence skip kar sakti hai. Kaunsa bada hai, aur kitna?

Step 1 — LCS (subsequence). Ex. 1 se, gaps allowed → length 4 (BCAB). Yeh step kyun? Mismatch branch $max (up, left)$ rakhta hai, toh progress mismatch survive karta hai — yahi cheez humein gaps jump karne deti hai.

Step 2 — LCSubstring ek alag recurrence use karta hai. Substrings ke liye, mismatch 0 par reset hota hai, aur answer sab cells par maximum hai, corner nahi:

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) .

Yeh step kyun? Contiguity ka matlab ek mismatch poora run todh deta hai; tum up/left se inherit nahi kar sakte.

Step 3 — dono mein sabse lamba contiguous run dhundo. AB pieces (...DABof X aurBDC**AB**`` of Y mein) aur CB extend nahi karte; sabse accha contiguous block length **2** (AB) hai. *Yeh step kyun?* ABCBDABka koi 3-letter contiguous chunkBDCAB` mein contiguously nahi milta.

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

Verify: substring ≤ subsequence hamesha (ek contiguous common block ek common subsequence bhi hai), aur $2 \leq 4$ ✅. Gap do recurrences ke beech "reset vs inherit" ka difference hai.

Coverage recap

Recall Kya humne har cell hit ki?

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. Recurrence ki har branch har degenerate condition mein exercise ki gayi. Kisi bhi LCS length par sabse tight general bounds ::: $0 \leq L (m, n) \leq min (m, n)$ — C3 mein 0 hit kiya, C4/C5/C7 mein $min$ hit kiya. Kaunsa cell LCS aur substring ko diverge hote dikhata hai ::: C9 (Ex. 9): 4 vs 2.

Active recall

ABCBDAB aur BDCAB ka LCS?

length 4 (BCAB ya BDAB).

Kisi bhi string aur "" ka LCS?

0 — akela base-case border hi.

Disjoint alphabets wali do strings ka LCS?

0 — match branch kabhi fire nahi karta.

Ek string ka khud ke saath LCS (length

k

k

— poori string; upper bound

min (m, n)

AAAA aur AA ka LCS?

2 — bottleneck As ki shorter supply hai.

ABCBDAB aur BDCAB ka Longest Common Substring?

2 (AB); substring mismatch par 0 par reset hoti hai.

LCS length par general bounds?

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

Ties multiple LCS kyun dete hain lekin same length?

equal up/left neighbours do optimal parents hain; dono length-optimal hain, alag witness strings.

Connections

Parent topic — woh recurrence jo yeh examples exercise karte hain.
Dynamic Programming — har example ke peeche table-filling paradigm.
Longest Common Substring — contiguous variant jo Ex. 9 mein contrast hua.
Edit Distance — same grid, alag cell rule; ek natural next stress test.
Longest Increasing Subsequence — LCS tak reduce hota hai; Ex. 8 ka token-LCS trick phir milta hai.
Diff Algorithm — Ex. 8 hi ek line-level diff hai.
Sequence Alignment — Ex. 8 ka DNA generalization.