3.7.10 · D5 · HinglishAlgorithm Paradigms
Question bank — DP problems — Longest Common Subsequence (LCS)
3.7.10 · D5· Coding › Algorithm Paradigms › DP problems — Longest Common Subsequence (LCS)
Pehle: is page par jo notation use hoti hai
Koi bhi question aane se pehle, hum har symbol ko zero se build karenge taaki is page par kuch bhi mystery na rahe.
Ab neeche har symbol — , , , , , — aur har direction word kisi aisi cheez ki taraf point karta hai jo tum pehle drawn dekh chuke ho.
True ya false — justify karo
Do strings ka LCS hamesha unme se kam se kam ek mein contiguous hota hai.
False. LCS characters dono strings mein gaps ke saath scattered ho sakte hain — jaise
AC, ABC aur AXC ka LCS hai, aur yeh kisi mein bhi contiguous nahi hai. Contiguity Longest Common Substring ki condition hai, is ki nahi.Agar do strings mein koi common character hi nahi hai, toh unka LCS length 0 hoga.
True. Koi common character nahi toh order mein rakhne ke liye kuch bhi nahi hai; mismatch se fill hone wali har cell un neighbours se inherit karti hai jo sab zero base row/column par trace back karte hain, toh .
Kisi bhi pair of strings ke liye LCS unique hota hai.
False. Ties hoti hain:
ABC aur ACB ka LCS length 2 hai jisme do valid answers AB aur AC hain. Sirf length unique hoti hai; string nahi.Dono strings ko reverse karne se LCS length change ho jaati hai.
False. LCS length dono inputs ko reverse karne par symmetric hoti hai, kyunki ulta padhaa gaya common subsequence reversed strings ka phir bhi common subsequence hota hai — same length.
Dono input strings ko swap karna () LCS length change kar sakta hai.
False. ; recurrence apne dono arguments mein symmetric hai (grid bas transpose ho jaati hai), toh corner value same rahti hai.
LCS length chhoti string ki length se zyada ho sakti hai.
False. Common subsequence dono ka subsequence hoti hai, isliye yeh kisi bhi input se lambi nahi ho sakti: (yaad karo , ).
Agar , ka ek subsequence hai, toh hoga.
True. khud dono mein common hai (yeh ke andar order mein hai), aur upar ke bound se koi se beat nahi kar sakta, isliye LCS exactly hai.
Traceback mein har diagonal step answer mein ek character add karta hai.
True — lekin sirf woh diagonal steps jo match par liye gaye hain. Diagonal move tabhi hota hai jab , aur tab hi ek shared character record hota hai, isliye match-diagonals aur answer-characters mein one-to-one correspondence hai.
Final answer hamesha DP table mein sabse bada value hota hai.
LCS ke liye False — answer hamesha corner hota hai. Table-wide max lena Longest Common Substring ka rule hai, jo mismatch par 0 reset karta hai.
Equal length ki do strings ka LCS us length ke barabar tab hi hoga jab strings identical hon.
True. hona force karta hai ki poora equally long ka common subsequence ho, jo tab hi possible hai jab character by character ho.
Error dhundho
"Mismatch par, ."
Yeh extra galat hai. Mismatches koi character add nahi karte; sahi rule hai (figure s03 mein up/left arrows). sirf diagonal match par milta hai.
"Match par, ."
Galat neighbour. Ek match diagonal prefix ko extend karta hai jo dono matched characters ko exclude karta hai: . Up/left use karna ek character double-count kar deta hai.
"Maine extra zero row aur column drop kar diya aur ko aur se index kiya."
Off-by-one bug. Code ki 0-indexed strings ke saath, cell ko aur compare karna chahiye, aur padded zero row/column empty-prefix base case implement karta hai.
"ABAB aur BABA anagrams hain, isliye unka LCS length 4 hai."
Anagrams letters share karte hain lekin necessarily order nahi. Unka LCS
BAB hai (length 3): dono mein relative order preserve karte hue aap sare chaar nahi rakh sakte."Maine table fill kiya lekin base row bhool gaya, ko 1 initialize kiya."
Ek empty prefix ka koi common subsequence nahi hota, isliye . 1 seed karna har downstream cell mein ek phantom character leak kar deta hai.
"Mismatch tie par (), mujhe 'up' hi choose karna chahiye warna answer galat hoga."
Yeh constraint galat hai. Dono directions ek equally long valid LCS dete hain; tie sirf yeh affect karta hai ki traceback ke dauran kaunsi string recover hogi, length kabhi nahi.
"Longest Increasing Subsequence ka LCS se koi lena-dena nahi."
Longest Increasing Subsequence array aur uski sorted-unique copy ke LCS par reduce hota hai, isliye yeh directly linked hain, unrelated nahi.
Why questions
Match par hum pair safely add kyun kar sakte hain bina chhota answer karne ke risk ke?
Kyunki prefixes ke kisi bhi optimal LCS ko is matching pair par end hone ke liye rewrite kiya ja sakta hai bina length khoye (ek exchange argument): agar optimum ne yeh pair use nahi ki, toh apna last kept letter is pair se swap karo — same length, phir bhi valid. Toh pairing kabhi worse nahi hoti, aur yeh dono prefixes ek ek se chhoti kar deti hai.
Match par specifically up-left (diagonal) kyun dekhte hain?
Match har string se ek character consume karta hai, isliye hume dono prefixes ek se chhoti karne par recurse karna hota hai — woh cell diagonally par hoti hai, exactly figure s03 mein diagonal arrow.
Mismatch par ek endpoint safely discard karna safe kyun hai?
Kyunki hai, ek LCS dono mein end nahi ho sakti, isliye kam se kam ek final character ke roop mein useless hai; less-useful ko drop karne se kuch nahi jaata, aur better branch choose karta hai (up vs left arrows).
LCS ek algorithm kyun hai na ki brute force ki tarah exponential?
Sirf distinct prefix subproblems hain — har grid cell ke liye ek; DP har ek ko ek baar compute karta hai aur reuse karta hai, choices ke exponential tree ko ek filled grid mein collapse kar deta hai.
Space tak reduce kyun ki ja sakti hai?
Har cell ko sirf current aur previous row chahiye (up, left, diagonal sab do rows ke andar rahte hain), isliye hum do rows roll karte hain aur chhoti dimension ko row length rakhte hain.
Edit Distance same grid kyun use karta hai lekin alag recurrence?
Dono ek prefix grid par chalte hain, lekin Edit Distance substitute/insert/delete moves bhi allow karta hai costs ke saath, isliye uski cell teen neighbours ko penalties ke saath combine karti hai na ki LCS ke match-reward ki tarah.
Edge cases
Jab dono strings empty hon toh LCS kya hogi?
Length 0. ke saath sirf cell hai base case ke hisaab se — koi letters nahi hain, toh kuch common nahi; yahi woh cornerstone hai jis par har doosri cell trace back karti hai.
Jab exactly ek string empty ho toh LCS kya hogi?
Length 0. Empty-prefix base case ise directly handle karta hai — ek side koi characters supply nahi karta, toh kuch bhi common nahi ho sakta.
Ek string ka khud se LCS kya hogi?
Poori string, length . Har character diagonal par match karta hai, isliye traceback main diagonal par chalta hai aur poora recover karta hai.
Jab strings ek doosre ke reverses hon, jaise ABC aur CBA, toh LCS kya hogi?
Yahan length 1 (koi bhi ek shared letter), kyunki ek mein kisi bhi do letters ko order mein rakhne se doosri mein opposite order force hota hai. Generally yeh longest palindromic-style common ordering hoti hai, aksar sirf 1.
Repeated characters ke saath kya hoga, jaise AAAA aur AA?
LCS length 2. Repeats theek hain; tum utne
As order mein match karte ho jitne chhoti string supply kar sakti hai, se bounded.Agar dono strings identical single characters hain, A aur A?
Length 1. Sirf diagonal cell par ek match deta hai.
Agar strings characters share karti hain lekin fully reversed order mein hain aur length badhti hai — kya table phir bhi sahi terminate hogi?
Haan. Content chahe kuch bhi ho, table finite hai aur har cell sirf already-filled up/left/diagonal neighbours par depend karti hai, isliye filling hamesha corner par answer ke saath terminate hoti hai.
Recall Ek-line survival kit
Match → diagonal ; miss → ; base (including both-empty); answer corner par; length unique, string nahi; se bounded.
Connections
- Parent topic — poori LCS derivation jis par yeh traps attack karte hain.
- Dynamic Programming — grid-filling mindset jo throughout assume ki gayi hai.
- Longest Common Substring — contiguous cousin jo mismatch par reset karta hai (sabse bade trap ka source).
- Edit Distance — same grid, richer moves.
- Longest Increasing Subsequence — LCS par reduce hota hai.