Overview
LCS (Longest Common Subsequence) — do strings ka sabse lamba common subsequence dhundho. DNA alignment, diff tools mein use.
Analogy
Jaise do playlists compare karo — kitne common songs hain same order mein.
Step-by-step
- dp[i][j] = LCS of first i chars of s1 aur j chars of s2
- Agar s1[i] == s2[j]: dp[i][j] = dp[i-1][j-1] + 1
- Nahi toh: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- Bottom-right se answer milta hai
Visual
s1="ABCBDAB", s2="BDCAB"
LCS = "BCAB" (length 4)
Multiple LCS possible hain
Common mistakes
- LCS length aur actual LCS string ka confusion
- Edit distance aur LCS alag hain
- Space optimization: only previous row needed
Practice questions
- LCS implement karo aur actual sequence print karo
- Shortest common supersequence LCS se nikalo