DP problems — Longest Common Subsequence (LCS): Exercises

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

Neeche do figures hain jo dikhate hain ki ek single cell kaise compute hoti hai aur diagonal "match" kaise travel karta hai.

Figure — DP problems — Longest Common Subsequence (LCS)

Level 1 — Recognition

L1.1 Inme se kaun sa ABCDE ka subsequence hai (order maintain karo, gaps allowed hain)? Har ek ke liye yes/no batao: ACE, AEC, BD, EDCBA, `` (empty).

Recall Solution L1.1

Left-to-right padhte hao; ek subsequence ko ABCDE ka relative order maintain karna zaroori hai.

ACE → yes (A…C…E sab order mein hain).
AEC → no (E, C se pehle aa raha hai, order toot gaya).
BD → yes (B…D).
EDCBA → no (reversed order).
`` empty → yes (sab kuch delete kar do; empty string har string ka subsequence hoti hai).

Yes-count = 3.

L1.2 Bina poora table banaye, inspection se har pair ki LCS length batao: (a) ABC vs ABC (b) ABC vs XYZ (c) AAAA vs AA (d) `` vs HELLO.

Recall Solution L1.2

(a) identical strings → poori string common hai → length 3.
(b) koi shared letter nahi → length 0.
(c) AA order mein AAAA ke andar fit hoti hai → length 2 (shorter string ki length se zyada kabhi nahi ho sakta).
(d) empty prefix → base case $L (0, j) = 0$ → length 0.

Level 2 — Application

L2.1 $X =$ AXY, $Y =$ AYZ ke liye DP table fill karo aur $L (3, 3)$ report karo.

Recall Solution L2.1

Rows = $X =$ AXY, cols = $Y =$ AYZ. Empty prefix ke liye extra zero row/column.

	A	Y	Z
""	0	0	0
A	1	1	1
X	1	1	1
Y	1	2	2

Cell (A,A): match → $1 + L (0, 0) = 1$ .
Cell (Y,Y): match → $1 + L ("AX", "A") = 1 + 1 = 2$ .
Saare mismatch cells $max (up, left)$ inherit karte hain.

Answer $L (3, 3) = 2$ , LCS = AY.

L2.2 $X =$ AGGTAB, $Y =$ GXTXAYB (parent ka Worked Example 1) ke liye corner 4 hai. Traceback karke LCS string do aur har string mein use kiye gaye indices list karo.

Recall Solution L2.2

Bottom-right corner se walk karo. Match → diagonally step lo aur letter prepend karo; mismatch → bade neighbour ki taraf move karo.

Built table follow karte hue, matched pairs (1-indexed) hain:

G : $x_{2} = y_{1}$
T : $x_{4} = y_{3}$
A : $x_{5} = y_{5}$
B : $x_{6} = y_{7}$

Bottom-up jaate hue prepend karne par GTAB milta hai, length 4.

$X$ indices used: ${2, 4, 5, 6}$ . $Y$ indices used: ${1, 3, 5, 7}$ .

L3.1 True ya false, har ek ke liye ek-line reason ke saath: (a) LCS length hamesha $\leq min (m, n)$ hoti hai. (b) Agar $X$ ke har letter distinct hain aur $X$ , $Y$ ka ek permutation hai, to $L (m, n) = m$ . (c) Dono input strings ko swap karne se LCS length badal jaati hai.

Recall Solution L3.1

(a) True. LCS dono ka subsequence hai, isliye ye shorter string se lamba nahi ho sakta. Agar $X$ mein $m$ letters hain to unme se $m$ se zyada select nahi kar sakte.
(b) False. Permutation letters ko reorder karta hai; order toot sakta hai. Example: $X =$ AB, $Y =$ BA permutations hain lekin $L = 1$ , $2$ nahi.
(c) False. $L (i, j)$ symmetric hai: swap ke baad recurrence matches aur dono neighbours ko identically treat karti hai, isliye $LCS (X, Y) = LCS (Y, X)$ . Swap sirf table ko transpose karta hai.

L3.2 ABCBDAB vs BDCAB consider karo. Corner 4 hai aur length 4 ke multiple LCS hain (BCAB aur BDAB). Explain karo ki traceback mein branching kahan hoti hai aur dono valid kyun hain.

Recall Solution L3.2

Traceback ke dauran tie tab aata hai jab current mismatch cell mein $L (up) = L (left)$ ho. Us fork par tum up ya left ja sakte ho, aur har direction ek equally long LCS tak le jaati hai.

ABCBDAB vs BDCAB ke liye, final B commit karne ke baad tum ek aise cell par pahunchte ho jahan "C-branch rakho" aur "D-branch rakho" dono value 3 hold karte hain. C route choose karne par BCAB banta hai; D route choose karne par BDAB banta hai.

Dono valid hain kyunki recurrence sirf length optimality guarantee karta hai, uniqueness nahi — ties ka matlab hai ki kaafi optimal witnesses exist karte hain. Corner value $L (m, n) = 4$ unique hai; string nahi.

Level 4 — Synthesis

L4.1 (LCS ↔ deletions) Tum sirf characters delete kar sakte ho. $X =$ AGGTAB ( $m = 6$ ) aur $Y =$ GXTXAYB ( $n = 7$ ) given hai jahan $L = 4$ hai, dono strings ko unke common subsequence mein convert karne ke liye kitne deletions chahiye? Ek formula aur number do.

Recall Solution L4.1

Har character jo LCS ka hissa nahi hai, delete karna hoga. $X$ se hum $L$ letters rakhte hain aur $m - L$ delete karte hain; $Y$ se $n - L$ delete karte hain. $deletions = (m - L) + (n - L) = m + n - 2 L .$ Yahan $= 6 + 7 - 2 (4) = 13 - 8 = 5$ .

Ye exactly deletion-only Edit Distance hai: $m + n - 2 L$ .

L4.2 (LIS via LCS) Bataya gaya hai ki LIS ko LCS ke roop mein compute kiya ja sakta hai. Array $A = [3, 1, 2, 1, 3]$ given hai, wo dono strings construct karo jinki LCS se LIS length milti hai, phir use compute karo.

Recall Solution L4.2

Construction: $B =$ $A$ ki sorted unique values. Tab $LIS (A) = LCS (A, B)$ , kyunki $A$ aur sorted-unique list ka common subsequence, $A$ ka ek subsequence hai jo strictly increasing bhi hai.

$A = [3, 1, 2, 1, 3]$
$B = sorted unique = [1, 2, 3]$

Ab $LCS ([3, 1, 2, 1, 3], [1, 2, 3])$ compute karo:

	1	2	3
""	0	0	0
3	0	0	1
1	1	1	1
2	1	2	2
1	1	2	2
3	1	2	3

LIS length = 3 (increasing subsequence 1,2,3).

Level 5 — Mastery

L5.1 (Space optimization) Parent $O (mn)$ space use karta hai. Explain karo ki length compute karne ke liye sirf do rows (ya ek rolling row) kyun kaafi hain, aur reduced space complexity state karo. Kaunsi capability tum kho dete ho?

Recall Solution L5.1

Recurrence dekho: cell $L (i, j)$ sirf row $i$ (uska left neighbour $L (i, j - 1)$ ) aur row $i - 1$ (up $L (i - 1, j)$ aur diagonal $L (i - 1, j - 1)$ ) par depend karta hai. Row $i - 1$ se upar kuch bhi dubara nahi padha jaata.

Isliye sirf previous row aur current row rakho: length $n + 1$ ke do arrays. Tum ise ek row plus ek saved "diagonal" scalar tak bhi compress kar sakte ho.

$Space = O (min (m, n))$ (shorter string ko columns ke along rakho).

Kya kho dete ho: poora table, isliye actual LCS string ko traceback karne ki ability. Tum sirf length recover kar sakte ho. String ke liye poora grid chahiye (ya Hirschberg's divide-and-conquer, jo $O (mn)$ time par $O (n)$ space aur string dono restore karta hai).

L5.2 (LCS vs Longest Common Substring same input par) $X =$ ABCBA, $Y =$ BCBAA ke liye dono compute karo: (a) LCS length, aur (b) longest common substring (contiguous) length. Wo ek rule dikhao jo differ karta hai.

Recall Solution L5.2

(a) LCS — mismatch $max (up, left)$ inherit karta hai; answer corner par.

	B	C	B	A	A
""	0	0	0	0	0
A	0	0	0	1	1
B	1	1	1	1	1
C	1	2	2	2	2
B	1	2	3	3	3
A	1	2	3	4	4

LCS length = 4 (BCBA).

(b) Longest common substring — ek changed rule: mismatch par 0 pe reset karo, aur answer kahin bhi maximum cell hai, corner nahi.

	B	C	B	A	A
""	0	0	0	0	0
A	0	0	0	1	1
B	1	0	1	0	0
C	0	2	0	0	0
B	1	0	3	0	0
A	0	0	0	4	1

Max cell = 4 (BCBA — yahan ye dono mein contiguously appear karta hai, isliye dono answers 4 par coincide karte hain). Structural difference: LCS corner padhta hai aur kabhi reset nahi karta; substring mismatch par reset karta hai aur global max scan karta hai. Dekho Longest Common Substring.

Recall Jaane se pehle ek-line self-test

Match rule? ::: diagonal $+ 1$ Mismatch rule (LCS)? ::: $max (up, left)$ , kabhi reset nahi Dono ko LCS par align karne ke liye deletions? ::: $m + n - 2 L$ Sirf length ke liye space? ::: $O (min (m, n))$ (traceback kho jaata hai)

Connections

Dynamic Programming — yahan har exercise ek 2-D table hai.
Edit Distance — L4.1 ka $m + n - 2 L$ deletion-only edit distance hai.
Longest Increasing Subsequence — L4.2 LIS ko LCS par reduce karta hai.
Longest Common Substring — L5.2 ka reset-to-0 contrast.
Diff Algorithm · Sequence Alignment — real-world LCS traceback.

Exercises — DP problems — Longest Common Subsequence (LCS)