# Longest Common Subsequence

- **Canonical ID**: `longest-common-subsequence`
- **Canonical URL**: https://dsacheatsheet.com/problems/longest-common-subsequence
- **Difficulty**: medium
- **Patterns**: 2D DP, Strings
- **Version**: 1.0.0 (verified 2026-11-11T21:20:00Z)
- **Original Problem**: https://leetcode.com/problems/longest-common-subsequence/

## 1. Core Invariant / The Trick

Rolling 1D DP tracking previous diagonal `diag`: if `text1[i] == text2[j]`, extend `diag + 1`; otherwise `max(dp[j], dp[j - 1])`. Space drops from `O(M * N)` to `O(min(M, N))`.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(M * N)`
- **Space Complexity**: `O(min(M, N))`
- **Proof**: Swap strings so shorter string dictates 1D row length `N`; each step reads current `dp[j]` (above), `prev` (left), and `diag` (top-left).

## 3. Minimal Idiomatic Code

### Python
```python
def longestCommonSubsequence(text1: str, text2: str) -> int:
    if len(text1) < len(text2):
        text1, text2 = text2, text1
    dp = [0] * (len(text2) + 1)
    for c1 in text1:
        diag = 0
        for j, c2 in enumerate(text2, 1):
            up = dp[j]
            dp[j] = diag + 1 if c1 == c2 else max(dp[j], dp[j - 1])
            diag = up
    return dp[-1]
```

### TypeScript
```typescript
export function longestCommonSubsequence(text1: string, text2: string): number {
  if (text1.length < text2.length) [text1, text2] = [text2, text1];
  const dp = new Int32Array(text2.length + 1);
  for (let i = 0; i < text1.length; i++) {
    let diag = 0;
    for (let j = 1; j <= text2.length; j++) {
      const up = dp[j];
      dp[j] = text1[i] === text2[j - 1] ? diag + 1 : Math.max(dp[j], dp[j - 1]);
      diag = up;
    }
  }
  return dp[text2.length];
}
```

### C++
```cpp
int longestCommonSubsequence(string s1, string s2) {
    if (s1.size() < s2.size()) swap(s1, s2);
    vector<int> dp(s2.size() + 1);
    for (char c1 : s1) {
        int diag = 0;
        for (size_t j = 1; j <= s2.size(); ++j) {
            int up = dp[j];
            dp[j] = (c1 == s2[j - 1]) ? diag + 1 : max(dp[j], dp[j - 1]);
            diag = up;
        }
    }
    return dp.back();
}
```

### Java
```java
int longestCommonSubsequence(String s1, String s2) {
    if (s1.length() < s2.length()) { String t = s1; s1 = s2; s2 = t; }
    int[] dp = new int[s2.length() + 1];
    for (int i = 0; i < s1.length(); i++) {
        int diag = 0;
        for (int j = 1; j <= s2.length(); j++) {
            int up = dp[j];
            dp[j] = s1.charAt(i) == s2.charAt(j - 1) ? diag + 1 : Math.max(dp[j], dp[j - 1]);
            diag = up;
        }
    }
    return dp[s2.length()];
}
```

### Go
```go
func longestCommonSubsequence(s1, s2 string) int {
    if len(s1) < len(s2) { s1, s2 = s2, s1 }
    dp := make([]int, len(s2)+1)
    for i := 0; i < len(s1); i++ {
        diag := 0
        for j := 1; j <= len(s2); j++ {
            up := dp[j]
            if s1[i] == s2[j-1] { dp[j] = diag + 1 } else { dp[j] = max(dp[j], dp[j-1]) }
            diag = up
        }
    }
    return dp[len(s2)]
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Failing to save `tmp = dp[j]` into `diag` *before* overwriting `dp[j]` loses the top-left diagonal value.

### Follow-ups
- Shortest Common Supersequence reconstructs through full 2D table of `dp[i][j]` with string length `M + N - LCS`.