# DP on Strings — Part 1: The Pattern

String DP problems come in two shapes. **Two strings** (LCS, edit distance, interleaving, regex): `dp[i][j]` describes the answer for the prefixes `a[:i]` and `b[:j]`, and each cell looks at the cell above, to the left and diagonally up-left. **One string, intervals** (palindromes): `dp[i][j]` describes the substring `s[i..j]`, built from shorter substrings inside it. Once you know which shape you're in, the recurrence almost writes itself.

![LCS table: matches extend the diagonal, mismatches take the better neighbour](diagrams/01-lcs-table.svg)

## 1. Two-String Template

```typescript
function lcs(a: string, b: string): number {
  const m = a.length, n = b.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 1; i <= m; i++)
    for (let j = 1; j <= n; j++)
      dp[i][j] = a[i - 1] === b[j - 1] ? dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1]);
  return dp[m][n];
}

function editDistance(a: string, b: string): number {
  const m = a.length, n = b.length;
  const dp = Array.from({ length: m + 1 }, (_, i) => Array.from({ length: n + 1 }, (_, j) => (i === 0 ? j : j === 0 ? i : 0)));
  for (let i = 1; i <= m; i++)
    for (let j = 1; j <= n; j++)
      dp[i][j] = a[i - 1] === b[j - 1] ? dp[i - 1][j - 1] : 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
  return dp[m][n];
}

function lcsEdit(a: string, b: string): number[] {
  return [lcs(a, b), editDistance(a, b)];
}
```

```python
def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]     # dp[i][j]: answer for a[:i], b[:j]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1    # match: extend the diagonal
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])   # drop one character
    return dp[m][n]

def edit_distance(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1): dp[i][0] = i              # delete everything
    for j in range(n + 1): dp[0][j] = j              # insert everything
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j],      # delete a[i-1]
                                   dp[i][j - 1],      # insert b[j-1]
                                   dp[i - 1][j - 1])  # replace
    return dp[m][n]

def lcs_edit(a, b):
    return [lcs(a, b), edit_distance(a, b)]
```

The extra row and column (index 0) represent the **empty prefix**, which makes base cases trivial: LCS with an empty string is 0; turning a prefix of length i into the empty string takes i deletions.

## 2. Reading the Neighbours

| Move into `dp[i][j]` from | Meaning in LCS | Meaning in edit distance |
|---|---|---|
| diagonal `dp[i−1][j−1]` | characters match: extend by 1 | match (free) or replace (+1) |
| above `dp[i−1][j]` | skip `a[i−1]` | delete `a[i−1]` (+1) |
| left `dp[i][j−1]` | skip `b[j−1]` | insert `b[j−1]` (+1) |

## 3. Palindromes: Expand Around Centres

For "longest palindromic substring" and "count palindromic substrings", an interval DP (`pal[i][j] = s[i] == s[j] and pal[i+1][j−1]`) works, but **expanding around each of the 2n − 1 centres** is simpler and uses O(1) space: grow outward while the characters match. Both are O(n²). (Manacher's algorithm is O(n) but rarely expected.)

## 4. Subsequence vs Substring

- **Substring** = contiguous: palindromic substring, longest common substring (reset to 0 on mismatch).
- **Subsequence** = order-preserving, gaps allowed: LCS, longest palindromic subsequence (= LCS of s and reversed s), distinct subsequences.

Mixing them up is the most common error in string DP questions; ask if the problem doesn't say.

## Under the Hood: Where Edit Distance Lives

`git diff` and `diff` compute a longest common subsequence of lines (Myers' algorithm, O((n + m)·D) for D differences) and print what isn't in it. Spell checkers rank suggestions by edit distance; DNA alignment (Needleman–Wunsch, Smith–Waterman) is edit distance with scoring matrices; fuzzy search (`pg_trgm`, Elasticsearch `fuzziness`) bounds it to keep queries fast.

## Common Pitfalls

1. **Off-by-one between dp indices and string indices:** `dp[i][j]` uses `a[i−1]`, `b[j−1]`.
2. **Forgetting the empty-prefix row/column** and its base values (edit distance needs `i` and `j`, not 0).
3. **Substring vs subsequence confusion.**
4. **Even-length palindromes:** expand from both a single centre `(i, i)` and a gap `(i, i+1)`.
5. **Memory:** O(m · n) tables for long strings; two rolling rows suffice when only the value is needed.

## Quick Reference

```text
two strings: dp[0][*], dp[*][0] = base; match → diagonal; else combine(above, left[, diagonal])
LCS: match +1 diag else max(up, left) · edit: match diag else 1 + min(up, left, diag)
palindromes: expand around 2n-1 centres, O(n^2) time, O(1) space
O(m · n) time; O(min(m, n)) space with rolling rows
```