Exercises — DP problems — edit distance (Levenshtein)

$dp[0][4]=4$. Row $i=0$ ka matlab hai "string $A$ zero letters contribute kar rahi hai" — woh empty hai. $B$ ke pehle 4 letters kuch nahi se banana ho, toh sirf insert ka move kaam aata hai jo letters add karta hai, aur tumhe exactly 4 chahiye. Koi sasta route nahi hai, isliye yeh ek base case hai, computed cell nahi.

Letters match karte hain, isliye $dp[i][j]=dp[i-1][j-1]$: pure diagonal, koi $+1$ nahi. Ek letter match karna free hai — tum is position pe na insert karte ho, na delete, na substitute.

• $dp[i-1][j]$ → $A$ se ek letter delete karo ($A$ ka prefix ek se chota hua, $B$ ka wahi raha).
• $dp[i][j-1]$ → $A$ mein ek letter insert karo ($B$ ka prefix chota hua, matlab $A$ ko woh extra letter chahiye tha).
• $dp[i-1][j-1]$ (differing letters) → substitute (dono prefixes chote hue aur letter swap karne ki cost di).

Right-to-left align karo. 't'='t' → free. 'a' vs 'u' → differ, ek substitute (+1). 'c'='c' → free. Total $=\boxed{1}$.

$A=$abc (rows), $B=$yabd (cols).

Bottom-right $dp[3][4]=\boxed{2}$. Path: aage y insert karo (+1), phir a,b free mein match, phir c→d substitute karo (+1). Ek insert + ek substitute = 2.

Har letter 'a' hai, toh kabhi koi substitution nahi chahiye — matches cost ko seedha diagonal se neeche le jaate hain. Sirf fark length mein hai: $A$ ke paas do extra 'a' hain. Dono delete karo → $\boxed{2}$. (Yahan yeh exactly length difference ke barabar hai kyunki koi letter kabhi change nahi karna pada.)

Jeetnewala neighbour hai $dp[4][3]=2$ (seedha upar wala cell). "Upar" ek delete from $A$ encode karta hai: hum horse ka trailing 'e' delete karte hain. Toh optimal path ka last move hai delete e, aur bacha hua cost 2 hors→ros fix karta hai. Baaki do options (substitute via $dp[4][2]=3$, insert via $dp[5][2]=4$) strictly zyada expensive the.

Har operation ka ek exact inverse of equal cost hota hai: $A$ mein ek letter ka insert undo hota hai us letter ke delete se (aur vice-versa); ek substitute x→y undo hota hai substitute y→x se. Toh koi bhi editing script jo $A$ ko $B$ mein $k$ moves mein turn karti hai, move-by-move reverse ho sakti hai $B$ ko $A$ mein same $k$ moves mein turn karne ke liye. Isliye ek taraf jo bhi cost achieve ho sakti hai woh doosri taraf bhi ho sakti hai, aur minimums equal hain: $d(A,B)=d(B,A)$.

$d(A,B)\ge |m-n|$. Reason: sirf insert aur delete ek string ki length change karte hain, aur har ek use exactly 1 se change karta hai. Substitute length unchanged chhod deta hai. Length $m$ se length $n$ tak jaane ke liye tumhe isliye kam se kam $|m-n|$ length-changing moves chahiye. Toh lengths ka difference ek floor hai, neeche kabhi nahi jaata — lekin yeh sirf ek lower bound hai, kyunki substitutions length change kiye bina cost add karti hain. horse(5)→ros(3) ke liye: bound hai $|5-3|=2$, lekin sahi answer 3 hai.

Substitution remove karne se min mein se "substitute" candidate delete ho jaata hai. Recurrence ban jaati hai:

Yeh exactly delete-both-then-reinsert cost hai, aur yeh Longest Common Subsequence se tied hai: distance $=m+n-2\cdot |\text{LCS}|$. cat→cut ke liye: LCS hai ct length 2 ka, toh distance $=3+3-2\cdot 2=\boxed{2}$. (Ek delete a ka, ek insert u ka — agar allowed hota toh single substitute se bhi ho jaata.)

Substitute term ka $+1$ ko $+2$ se replace karo:

Single mismatch a vs u ke liye: substitute cost 2, lekin delete-a + insert-u bhi cost $1+1=2$ hai — ek tie at $\boxed{2}$. General rule: jab substitution cost $\ge 2$ ho, delete+insert hamesha kam se kam utna hi achha hai, toh substitution kabhi strictly nahi jeetti.

$A=$ab (rows), $B=$ba (cols). Row 0 (base) hai $[0,1,2]$.

Row 1 compute karo (A[0]='a'), sirf row 0 padhte hue:

• $dp[1][0]=1$ (base column).
• $j=1$, 'a' vs 'b' differ karte hain → $1+\min (\text{diag }0,\text{up }1,\text{left }1)=1$.
• $j=2$, 'a' vs 'a' match → diagonal $=dp[0][1]=1$.

Row 1 $=[1,1,1]$. Row 0 discard karo, row 1 ko "previous" rakhho.

Row 2 compute karo (A[1]='b'), sirf row 1 padhte hue:

• $dp[2][0]=2$ (base column).
• $j=1$, 'b' vs 'b' match → diagonal $=$ prev$[0]=1$.
• $j=2$, 'b' vs 'a' differ karte hain → $1+\min (\text{diag prev}[1]=1,\text{up prev}[2]=1,\text{left }dp[2][1]=1)=2$.

Row 2 $=[2,1,2]$. Answer $=dp[2][2]=\boxed{2}$ (ab→ba swap karne mein do edits lagte hain: dono substitute karo, ya delete+insert). Humhe kabhi poora grid nahi chahiye tha — do rows kaafi the kyunki recurrence sirf row $i-1$ padhti hai.

Sach hai. Koi shared letter nahi hone se koi diagonal match kabhi free nahi hoga. Overlapping positions reconcile karne ka sabse sasta tarika hai unhe substitute karna (cost 1 each) pehle $\min (m,n)$ positions ke liye, phir baaki $|m-n|$ leftover letters ke liye insert ya delete karna (cost 1 each). Total $=\min (m,n)+|m-n|=\max (m,n)$. Koi route isse beat nahi kar sakta: tumhe saare $\max (m,n)$ positions account karne hain, aur har ek kam se kam 1 cost karta hai kyunki kuch match nahi karta. Toh $d=\boxed{\max (m,n)}$.

Har letter differ karta hai (x vs y), lengths equal hain, toh koi length change nahi chahiye aur $k$ aligned positions mein se har ek ko ek substitute chahiye. Closed form: $d=k$. Check $k=3$: "xxx"→"yyy" ko 3 substitutions chahiye $=\boxed{3}$. Yeh ek clean regression test hai kyunki answer exactly linearly $k$ ke saath scale karta hai.

Traceback rule: har cell pe, dekho kaun se neighbour ne ise produce kiya.

• Start $dp[3][4]=2$ (c vs d, differ). Yeh $1+dp[2][3]$ ke barabar hai diagonal se → substitute c→d. $dp[2][3]=1$ pe jao.
• $dp[2][3]=1$ (b vs b, match) → diagonal $dp[1][2]=1$ se aaya, koi move nahi. $dp[1][2]$ pe jao.
• $dp[1][2]=1$ (a vs a, match) → diagonal $dp[0][1]=1$, koi move nahi. $dp[0][1]$ pe jao.
• $dp[0][1]=1$ row 0 pe hai → $B$ mein y abhi bhi account karna hai → insert y. $dp[0][0]=0$ pe pohoncho. Ho gaya.

Forwards padhne par: insert y, a rakho, b rakho, substitute c→d → exactly 2 edits, table se match karta hai. Yahi traceback wajah hai ki poora grid store karna (sirf ek row ki jagah) worth it hai jab tumhe script chahiye, sirf number nahi.

$d(\text{"cat"},\text{"cut"})$ sab costs 1 ke saath ::: 1 $d(\text{"aaaa"},\text{"aa"})$ ::: 2 $d(\text{"abc"},\text{"yabd"})$ ::: 2 cat,cut ki insert-and-delete-only distance ::: 2 (equals $m+n-2\cdot \text{LCS}$) Lengths se $d$ ka lower bound ::: $|m-n|$ $d(\text{"xxx"},\text{"yyy"})$ ::: 3 Jab strings mein koi common letter nahi toh distance ::: $\max (m,n)$