DP problems — Longest Common Subsequence (LCS)

3.7.10 · Coding › Algorithm Paradigms

WHAT hai LCS (vs. substring)

WHY care? LCS diff tools, version control merges, DNA/protein alignment, aur plagiarism detection ko power karta hai. Yeh canonical 2-D dynamic-programming problem hai.

HOW derive karein recurrence (scratch se)

Maano do strings hain $X=x_1{x}_2\dots x_m$ aur $Y=y_1{y}_2\dots y_n$.

Define karo $L(i,j)=\text{length of LCS of the prefixes }X[\mathrm{1..}i]\text{ and }Y[\mathrm{1..}j].$

Hume chahiye $L(m,n)$.

LAST characters $x_i$ aur $y_j$ ke baare mein socho. Ya toh woh match karte hain ya nahi.

Case 1 — woh match karte hain ($x_i=y_j$). Yeh shared character safely LCS ko end kar sakta hai. Kyun? Kyunki agar in prefixes ka optimal LCS is matching pair ko use nahi karta, toh hum hamesha is pair ko swap in kar sakte hain bina length khoye (neeche steel-manned hai). Toh unhe pair karo aur chote prefixes pe recurse karo: $L(i,j)=1+L(i-1,j-1).$

Case 2 — woh match nahi karte ($x_i\ne y_j$). LCS DONO $x_i$ aur $y_j$ ko apna final character nahi bana sakta (woh differ karte hain). Toh unme se kam se kam ek endpoint ke roop mein useless hai — ek ko drop karo aur better option lo: $L(i,j)=\max (L(i-1,j),L(i,j-1)).$

Base case. Ek empty prefix ka koi common subsequence nahi hota: $L(0,j)=L(i,0)=0.$

DP table

Hum ek $(m+1)\times (n+1)$ table row by row fill karte hain. Har cell upper-left (diagonal) dekhti hai jab characters match karein, warna up aur left.

Worked Example 1 — AGGTAB vs GXTXAYB

Worked Example 2 — actual string recover karna (traceback)

Chhota dry run jo tumhe mentally karna chahiye

Common mistakes (steel-manned)

Reference implementation

def lcs(X, Y):
    m, n = len(X), len(Y)
    L = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[j-1]:
                L[i][j] = 1 + L[i-1][j-1]   # match: diagonal + 1
            else:
                L[i][j] = max(L[i-1][j], L[i][j-1])
    return L[m][n]

Active recall

Connections

• Dynamic Programming — LCS textbook 2-D table DP hai.
• Edit Distance — same grid; insert/delete/replace costs LCS ko generalize karte hain.
• Longest Common Substring — contiguous variant; mismatch pe reset hoti hai.
• Longest Increasing Subsequence — LIS, array aur uski sorted-unique copy ke LCS mein reduce hoti hai.
• Diff Algorithm — git diff LCS-based hai.
• Sequence Alignment — Needleman–Wunsch bioinformatics version.

Concept Map