Visual walkthrough — DP problems — Longest Common Subsequence (LCS)

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

Hum poore walkthrough mein do chhoti strings use karte hain taaki har cell dikh sake: $X=\text{AGCAT},Y=\text{GAC}.$

Step 1 — "Subsequence" ka matlab kya hai (sliding picture)

KYA. Ek subsequence woh hoti hai jo tum kisi string mein left-to-right chalte hue banate ho — har character par rakhna ya chhod dena choose karte ho — kabhi order nahi badalta.

KYU. LCS ki poori baat is ek rule mein band hai: order sacred hai, gaps free hain. Agar "gaps free hain" bhool gaye toh Longest Common Substring mein ghus jaoge; agar "order sacred hai" bhool gaye toh ek set milega, sequence nahi.

PICTURE. Neeche diye figure mein AGCAT upar hai. Green highlighted letters A_C_T (G aur A ko skip karke) ek valid subsequence banate hain: rakhe gaye letters left-to-right chalte hain. Red wala attempt A_C_A order badal raha hai? — yeh impossible hai, tum peeche nahi chal sakte.

Step 2 — Goal ka naam: prefix quantity $L(i,j)$

KYA. Hum ek number invent karte hain. $X$ ke pehle $i$ letters aur $Y$ ke pehle $j$ letters padho — inhe prefixes kaho. Toh $L(i,j)=\underset{\text{sirf ek count}}{\underbrace{\text{length}}}\text{ of the longest common subsequence of }\underset{\text{pehle }i\text{ of }X}{\underbrace{X[\mathrm{1..}i]}}\text{ and }\underset{\text{pehle }j\text{ of }Y}{\underbrace{Y[\mathrm{1..}j]}}.$

KYU ek prefix quantity? Kyunki AGCAT vs GAC ko ek hi jump mein solve nahi kar sakte. Hum ek grid banate hain jahan har cell usi sawal ka ek chhota version hai. Chhotey waalon ko solve karo, bade waalon ke liye unhe reuse karo — yahi reuse Dynamic Programming ki poori idea hai.

PICTURE. Grid: rows $X$ ke prefixes hain (neeche badhte hue), columns $Y$ ke prefixes hain (daayein badhte hue). Row $i$, column $j$ wala cell hi number $L(i,j)$ hai. Humara final answer shaded bottom-right corner mein rehta hai.

Step 3 — LAST characters kyun dekhte hain?

KYA. Cell $L(i,j)$ fill karne ke liye hum sirf do nayi letters dekhte hain: $x_i$ ($X$ ka $i$-vaa letter) aur $y_j$ ($Y$ ka $j$-vaa letter).

KYU sirf last? Prefixes ki subsequence kahan na kahan khatam hogi. Ya toh bilkul last letters us khatam hone mein kaam aate hain, ya nahi aate. Yeh ek clean two-way split hai — aur two-way split hi woh hai jo recurrence ko chahiye. Beech ke baare mein sochne ki zaroorat nahi.

PICTURE. Do prefix bars, ek har string ke liye, jisme har ek ka final letter circle kiya gaya hai. Circles ke beech ek hinge hai jo ek sawal poochh raha hai: same letter, ya alag? Do darwaaze bahar jaate hain — "match" darwaaza aur "mismatch" darwaaza.

Step 4 — MATCH darwaaza: $x_i=y_j$

KYA. Maan lo do nayi letters equal hain. Toh hum us shared letter ko pakad lete hain, use apne LCS ki ending ke roop mein pair karte hain, aur dono prefixes ko ek se chhota kar dete hain: $L(i,j)=\underset{\begin{array}{c}\text{naaya}\\ \text{shared letter}\end{array}}{\underbrace{1}}+\underset{\begin{array}{c}\text{dono prefixes ka best LCS,}\\ \text{ek ek chhota}\end{array}}{\underbrace{L(i-1,j-1)}}.$

KYU $+1$, aur KYU diagonal cell? $+1$ isliye kyunki genuinely naaya shared character mila. Hum $L(i-1,j-1)$ — diagonal neighbour — mein recurse karte hain, kyunki dono strings se ek letter consume karna ek row upar aur ek column baayein dono at once lejata hai. Woh ek diagonal step hi "dono letters use karo" hai.

Kya pair pakadna hamesha safe hai? Haan. Agar koi optimal LCS alag tarike se khatam hoti, toh tum uski ending ko is matched pair se replace kar sakte ho bina use chhota kiye — toh pairing mein kuch nahi jaata. (Yeh woh exchange argument hai jo parent note ne steel-man kiya tha.)

PICTURE. Dono final letters C hain. Ek diagonal arrow diagonal neighbour se current cell mein jump karta hai, value lekar aata hai aur ek add karta hai.

Step 5 — MISMATCH darwaaza: $x_i\ne y_j$

KYA. Ab nayi letters alag hain. Dono ek hi common subsequence ka final letter nahi ho sakte (ek sequence ki ek hi ending hoti hai, aur yeh do letters agree nahi karte). Toh unme se kam se kam ek endpoint ke roop mein bekaar hai — ek ko throw away karo aur jo better option bacha ho use rakho: $L(i,j)=\max (\underset{\begin{array}{c}{x}_i\text{ drop karo,}\\ \text{upar dekho}\end{array}}{\underbrace{L(i-1,j)}},\underset{\begin{array}{c}{y}_j\text{ drop karo,}\\ \text{baayein dekho}\end{array}}{\underbrace{L(i,j-1)}}).$

KYU $+1$ nahi? Koi naaya shared character nahi mila, isliye kuch earn nahi hua. Hum sirf thoda chhote problem ka already computed best answer inherit kar rahe hain.

KYU up aur left ka max (kabhi diagonal nahi)? "$x_i$ drop karo" matlab $X$ ka prefix chhota karo — woh hai up neighbour $L(i-1,j)$. "$y_j$ drop karo" matlab $Y$ ka prefix chhota karo — woh hai left neighbour $L(i,j-1)$. Hum pehle se nahi jaante kaun sa discard smarter hai, isliye dono try karte hain aur bada rakhte hain. Diagonal yahan forbidden hai: dono letters drop karna kisi ek taraf chupi match ko throw away kar sakta hai.

PICTURE. Final letters T vs C disagree karte hain. Do arrows — ek upar se, ek baayein se — current cell ko feed karte hain; mota arrow (badi value) jeetta hai.

Step 6 — Floor: empty prefixes se zero milta hai

KYA. Recurrence prefixes ko chhota karte karte kahin rukna chahiye. Jab koi bhi prefix empty ho ($i=0$ ya $j=0$) toh share karne ke liye kuch nahi hai: $L(0,j)=0,L(i,0)=0.$

KYU yeh base case? Empty string mein koi character nahi, isliye woh kisi ke saath kuch bhi share nahi karti — length-0 LCS. Yeh zeros top row aur left column banate hain aur baad waaley har cell ko seed karte hain. Inke bina recursion grid ke edge se gir jaati.

PICTURE. Grid jisme poori top row aur left column 0s se pre-filled hain (burnt-orange border). Baaki har cell is border se compute ki jaayegi.

Step 7 — AGCAT vs GAC ke liye poora grid fill karo

KYA. Row by row sweep karo, left to right. Har cell apna darwaaza choose karta hai (Step 4 ya Step 5) aur apne already-finished neighbours se padh leta hai.

KYU row-by-row order? Har cell ko apne up, left, aur diagonal neighbours chahiye — jo sab upar ya baayein hote hain. Toh agar hum top-to-bottom, left-to-right fill karein, toh zaroorat padne se pehle har neighbour guaranteed ready hoga.

PICTURE. Completed $6\times 4$ table. Diagonal (match) steps teal mein hain, max (mismatch) inheritances plum mein. Kuch cells follow karo aur unhe rules se check karo.

Step 8 — Traceback: actual string recover karna

KYA. Corner length deta hai. Letters paane ke liye, corner se backward chalo, har cell ko banane waaley arrow ke saath.

KYU backward chalna kaam karta hai? Har cell yaad rakhta hai kaise bana tha. Ek diagonal (+1) cell matlab "yeh shared letter LCS mein hai — isse record karo, phir diagonally step karo." Ek max cell matlab "yahan koi letter nahi — jis neighbour se copy kiya tha uski taraf step karo." Construction ko reverse karo aur letters bahar aa jaate hain (ulte order mein, toh end mein unhe ulta padho).

PICTURE. Bottom-right se top-left tak ek path. Teal diagonal steps collected letters mark karte hain (C, phir G); plum straight steps kuch collect nahi karte. Collected letters top-down padho toh GC banta hai.

Ek-picture summary

KYA. Ek diagram poora page compress karta hai: do letters ek decision mein enter karte hain, aur answer teen neighbours mein se ek se flow karta hai.

Related build-outs

• Dynamic Programming — subproblems ka reuse idea jo Step 2 ko power deta hai.
• Edit Distance — same grid, lekin mismatches par max ki jagah replace cost lagti hai.
• Longest Common Substring — Step 5 ko "reset to 0" se swap karo, max over all cells padho.
• Longest Increasing Subsequence — array ko uske sorted-unique copy ke saath LCS mein reduce ho jaata hai.
• Diff Algorithm — Step 8 ka traceback exactly git diff hai.
• Sequence Alignment — is grid ka biology-flavoured Needleman–Wunsch version.

Active recall