Longest Common Subsequence (LCS)

1. One-Liner

LCS fills dp[i][j] with the LCS length for prefixes A[0..i) and B[0..j) using match/mismatch transitions.

2. The Problem It Solves

Given two sequences, find the longest strictly increasing-in-index common subsequence—characters must appear in order but not necessarily contiguously.

3. The Core Idea

If A[i-1]==B[j-1], extend LCS by 1; else take the better of dropping one character from either side—optimal substructure on prefixes.

4. How It Works (Step-by-Step)

Step	What Happens
1	`dp[i][0]=dp[0][j]=0`
2	If match: `dp[i][j]=1+dp[i-1][j-1]`
3	Else: `max(dp[i-1][j], dp[i][j-1])`
4	Answer `dp[n][m]`; backtrack for string

5. Dry Run Example

"abc" vs "ac": LCS "ac", length 2.

6. Key Properties

Property	Value
Time	O(`nm`)
Space	O(`min(n,m)`) possible

7. Where It Is Used

Domain	Use
Diff / Git	Line comparison
Bioinformatics	Sequence alignment baseline

8. Interview Tips

Know print LCS, space optimization, and LCS → shortest supersequence relation.

9. Comparison with Other Algorithms

Problem	Focus
LCS	Order, not necessarily contiguous
LCSubstring	Contiguous segment—different DP

10. Complexity

Metric	Value
Time	O(`nm`)
Space	O(`nm`) or O(`min(n,m)`)

Implementation Example (PYTHON)

def lcs_length(a: str, b: str) -> int:
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]