3.7.10 · D1DP problems — Longest Common Subsequence (LCS)
Do strings ek "skeleton" share karti hain — kuch letters jo dono mein milte hain, same left-to-right order mein, lekin gaps allowed hain — woh skeleton hi Longest Common Subsequence hai. Parent page par baaki sab sirf bookkeeping hai: hum dono strings ko prefixes mein kaatate hain, har prefix-vs-prefix answer ko ek do-number label L ( i , j )
Is page par yeh assume kiya gaya hai ki tumne kuch nahi dekha . Hum har woh letter, arrow, aur bracket banate hain jis par parent LCS note ek-ek brick se rely karta hai. Agar neeche koi term already obvious lage, skim karo — lekin har ek jagah hai jahan beginners silently trip karte hain.
Ek string bas characters (letters/symbols) ki ordered list hoti hai, jo left to right padhi jaati hai. Hum ise code font mein likhte hain: ABCBDAB.
"Ordered" ka matlab hai ki position matter karti hai: AB aur BA same string nahi hain.
String ki length woh count hai kitne characters usme hain. ABCBDAB ki length 7 hai.
Picture: socho ek seedhe wire par beads. Har bead ek character hai, aur wire unka order fix karti hai — bead 4 ko bead 2 ke aage slide nahi kar sakte wire kaate bina.
Topic ko yeh kyun chahiye. LCS do aisi wires ko compare karta hai aur poochta hai ki kaunse beads dono mein line up hote hain, wire ka order intact rakhte hue. Agar fixed order na hota, toh protect karne ke liye koi "same relative order" hi nahi hoti.
Parent likhta hai X = x 1 x 2 … x m Y = y 1 y 2 … y n
X , Y , x i , y j , m , n
X Y do poori strings ke naam hain jo hum compare karte hain. Capital letters use karna matlab "poori string".x i i X i character "." Toh agar X = AGGTAB, toh x 1 = A, x 2 = G, x 4 = T.y j Y j m X n Y x 1 … x m y 1 … y n
Intuition Har baar nayi letter ki jagah subscript kyun?Subscript ek pointer hai: first, second, third jaise naye naam banane ki jagah, hum kehte hain "mujhe character number i i i j X Y
Picture: beads ki do rows stacked. Ek finger jis par i X j Y
x i Kyun sahi lagta hai: x i Fix: yahan koi multiplication nahi hai. Subscript ek address hai, jaise "X i x i
Yahi THE distinction hai jis par poora topic tika hai.
Definition Subsequence aur substring
Ek subsequence woh hota hai jo bachta hai jab hum kuch characters delete karein (ya koi nahi) bina baaki ko reorder kiye . Gaps allowed hain.
Ek substring ek contiguous block hota hai — koi gaps nahi, tum ek solid run ko bina holes ke slice karte ho.
Picture — same string, do alag rules:
ABCDE se:
ACE ek subsequence hai (A rakho, B skip, C rakho, D skip, E rakho — order preserved, gaps allowed).ACE ek substring nahi hai (A, C, E ek doosre ke paas nahi hain).BCD ek substring hai (ek solid slice).
Intuition "Same order but gaps allowed" LCS ka dil kyun haiJo letters tum rakhte ho woh original ki tarah left-to-right same sequence mein appear hone chahiye — tum skip kar sakte ho, lekin tum kabhi reshuffle nahi kar sakte. Yahi ek freedom (skip) aur ek restriction (no reorder) exactly wahi hai jo LCS ko "equal letters dhundho" se harder aur "equal blocks dhundho" se easier banata hai.
Topic ko yeh kyun chahiye. LCS = dono strings mein common sabse lamba subsequence . Ise substring se confuse karna ek bilkul alag recurrence deta hai (parent ke mistake box mein dekho). Yeh abhi pakad lo aur aadhe traps gayab ho jaate hain. Contiguous cousin Longest Common Substring mein rehta hai.
Definition Prefix aur notationX [ 1.. i ] prefix ek string ka starting chunk hota hai: left se pehle kuch characters, bina kisi skip ke.
X [ 1.. i ] X 1 i
X [ 1..0 ] empty prefix (zero characters, "" likha jaata hai).AGGTAB ka X [ 1..3 ] AGG.X [ 1.. m ] X
Picture: ek sliding cut. Position i left mein sab kuch prefix X [ 1.. i ]
Intuition Arbitrary chunks ki jagah prefixes kyun?LCS problem ko shrink karke solve hoti hai. Agar hum chhote i , j X pehle i aur Y pehle j ka LCS" answer kar sakein, toh hum poori strings tak build up kar sakte hain. Prefixes natural shrinking unit hain kyunki hum hamesha right end se kaatate hain (last character dekho, phir peeche jaao). Yeh single design choice hi wajah hai ki recurrence exist karti hai.
L ( i , j ) L ( i , j ) = length of the LCS of the prefixes X [ 1.. i ] and Y [ 1.. j ] . L i j X i Y j
L L function hai: tum ise do numbers ( i , j ) i j lookup box socho; har dial setting ek stored answer reveal karti hai. Kyunki i ( m + 1 ) j ( n + 1 )
"Length" kyun, khud string kyun nahi? Lengths single numbers hain, compare karna aur add karna trivial hai. Hum pehle saari lengths compute karte hain (fast), phir ek actual string recover karne ke liye sirf tabhi backwards chalte hain jab chahiye (parent ka traceback). "Kitni lambi" aur "kaunse letters" ko alag rakhna core ko simple rakhta hai.
Jo final answer chahiye woh hai L ( m , n )
Parent ki formula do operations use karti hai. Dono ek plain-words picture deserve karti hain.
max ( a , b ) max do numbers mein se bada lo "." max ( 3 , 5 ) = 5 max ( 2 , 2 ) = 2
+ max differ karein, toh dono ek saath common subsequence ko cap nahi kar sakte. Hume ek character drop karna hoga aur dobara try karna hoga — ya toh X L ( i − 1 , j ) Y L ( i , j − 1 ) winner rakhte hain . max hota hai . Unhe add karna double-count karta; max lena kabhi over-count nahi karta.
+ 1 equal hain (x i = y j end par baith sakta hai. Hum ise exactly + 1 X [ 1.. i − 1 ] Y [ 1.. j − 1 ] har ek string se ek character "use" kar liya. Wahi "ek har ek se" wajah hai ki hum dono dials ek saath peeche jaate hain (the diagonal). Ek mismatch koi naya shared letter supply nahi karta, isliye usे + 0
Definition Do cases words mein
Match (x i = y j L ( i , j ) = 1 + L ( i − 1 , j − 1 ) Mismatch (x i = y j L ( i , j ) = max ( L ( i − 1 , j ) , L ( i , j − 1 ) )
Yahan = = test hai ("kya yeh do characters same hain?"), assignment nahi.
L ( 0 , j ) = L ( i , 0 ) = 0 koi bhi prefix empty hai (zero characters), share karne ko kuch nahi, isliye LCS length 0
Picture: ek empty wire mein koi beads nahi hain; koi bead kuch nahi ke against match nahi kar sakti. Toh grid mein row 0 0 0
m × n ( m + 1 ) × ( n + 1 ) 0 extra row (i = 0 extra column (j = 0 off-by-one ka source bhi hai: code mein, cell L [ i ] [ j ] X [ i − 1 ] Y [ j − 1 ] 0 1
Har bhara hua cell L ( i , j ) teen pehle-computed neighbours se decide hota hai:
Definition Teen neighbours
up = L ( i − 1 , j ) X left = L ( i , j − 1 ) Y diagonal (up-left) = L ( i − 1 , j − 1 ) dono ka ek kam.
Picture: ek cell par khado. Match rule diagonal tak pahunchti hai (dono dials neeche). Mismatch rule up aur left tak pahunchti hai aur bada rakhti hai. Yeh directional habit — "match diagonal jaata hai, miss max leta hai" — poora mechanical skill hai.
Recall Kaun se case ke liye kaun sa neighbour?Match kaun sa neighbour use karta hai? ::: Diagonal (up-left), plus 1.
Mismatch kaun se neighbours use karta hai? ::: Up aur left, max lo.
String = ordered characters
Index x_i, y_j pointers into strings
Subsequence keeps order allows gaps
Function L i,j returns a length
max operation keep the bigger
Empty prefix means length 0
LCS recurrence match diagonal miss max
Right side cover karo aur khud test karo. Agar koi bhi answer fuzzy lage, parent ki derivation tackle karne se pehle woh section dobara padho.
x i String X i
m n Respectively X Y
Subsequence aur substring mein kya farq hai? Subsequence order rakhta hai lekin gaps allow karta hai (skips); substring contiguous hona chahiye (koi gaps nahi).
Prefix X [ 1.. i ] X i
X [ 1..0 ] Empty prefix "" — zero characters.
Plain words mein L ( i , j ) X i Y j
L Ek function (ek two-dial lookup box) jo do numbers leta hai aur ek length return karta hai.
max ( a , b ) a , b
Match exactly + 1 Ek shared letter end ke liye mila; woh har string se ek character use karta hai, isliye dono prefixes ek se shrink hote hain (diagonal).
Base case 0 Ek empty prefix mein koi characters nahi hain, isliye kuch share nahi ho sakta.
Grid m × n ( m + 1 ) × ( n + 1 ) Index 0 par "empty prefix" zeros ki row/column hold karne ke liye, taaki har cell ke safe up/left/diagonal neighbours hon.
Final answer kaun sa cell hold karta hai? Bottom-right corner L ( m , n )
