DP problems — Longest Common Subsequence (LCS)

WHAT is LCS (vs. substring)

WHY care? LCS powers diff tools, version control merges, DNA/protein alignment, and plagiarism detection. It is the canonical 2-D dynamic-programming problem.

HOW to derive the recurrence (from scratch)

Let the two strings be $X = x_1 x_2 \dots x_m$ and $Y = y_1 y_2 \dots y_n$.

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

We want $L(m, n)$.

Think about the LAST characters $x_i$ and $y_j$. Either they match or they don't.

Case 1 — they match ($x_i = y_j$). This shared character can safely end the LCS. Why? Because if an optimal LCS of these prefixes does NOT use this matching pair, we can always swap in this pair without losing length (steel-manned below). So pair them up and recurse on the smaller prefixes: $L(i,j) = 1 + L(i-1, j-1).$

Case 2 — they don't match ($x_i \ne y_j$). The LCS cannot use BOTH $x_i$ and $y_j$ as its final character (they differ). So at least one of them is useless as an endpoint — drop one and take the better option: $L(i,j) = \max\big(L(i-1, j),\; L(i, j-1)\big).$

Base case. An empty prefix has no common subsequence: $L(0, j) = L(i, 0) = 0.$

The DP table

We fill a $(m+1)\times(n+1)$ table row by row. Each cell looks up-left (diagonal) when characters match, otherwise up and left.

Worked Example 1 — AGGTAB vs GXTXAYB

Worked Example 2 — recovering the actual string (traceback)

Small dry run you should do mentally

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 is the textbook 2-D table DP.
• Edit Distance — same grid; insert/delete/replace costs generalize LCS.
• Longest Common Substring — contiguous variant; resets on mismatch.
• Longest Increasing Subsequence — LIS reduces to LCS of array and its sorted-unique copy.
• Diff Algorithm — git diff is LCS-based.
• Sequence Alignment — Needleman–Wunsch bioinformatics version.

Concept Map

Hinglish (regional understanding)