# DP on Strings — Part 2: Interview Problems

Six problems: the two-string table family (LCS, edit distance, interleaving, regex) and centre expansion for palindromes.

## 1. Longest Common Subsequence (LeetCode 1143)

**🟠 Medium.** Return the length of the longest subsequence common to `text1` and `text2`.

```text
"abcde", "ace" → 3
```

**Approach.** `dp[i][j]` = LCS of `text1[:i]` and `text2[:j]`. Matching last characters extend the diagonal by 1; otherwise take the better of dropping one character from either string.

**Complexity.** O(m · n) time, O(min(m, n)) space with rolling rows.

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

```python
def longest_common_subsequence(a, b):
    prev = [0] * (len(b) + 1)
    for i in range(1, len(a) + 1):
        cur = [0] * (len(b) + 1)
        for j in range(1, len(b) + 1):
            cur[j] = prev[j - 1] + 1 if a[i - 1] == b[j - 1] else max(prev[j], cur[j - 1])
        prev = cur
    return prev[-1]
```

## 2. Edit Distance (LeetCode 72)

**🟠 Medium.** Return the minimum number of insertions, deletions and replacements to turn `word1` into `word2`.

```text
"horse" → "ros" = 3   (replace h→r, delete r, delete e)
```

**Approach.** `dp[i][j]` = edits to turn `word1[:i]` into `word2[:j]`. Base: `dp[i][0] = i`, `dp[0][j] = j`. If the last characters match, take the diagonal; otherwise 1 + the minimum of delete (above), insert (left) and replace (diagonal).

**Complexity.** O(m · n) time, O(n) space with rolling rows.

```typescript
function minDistance(a: string, b: string): number {
  let prev = Array.from({ length: b.length + 1 }, (_, j) => j);
  for (let i = 1; i <= a.length; i++) {
    const cur = [i, ...new Array(b.length).fill(0)];
    for (let j = 1; j <= b.length; j++)
      cur[j] = a[i - 1] === b[j - 1] ? prev[j - 1] : 1 + Math.min(prev[j], cur[j - 1], prev[j - 1]);
    prev = cur;
  }
  return prev[b.length];
}
```

```python
def min_distance(a, b):
    prev = list(range(len(b) + 1))
    for i in range(1, len(a) + 1):
        cur = [i] + [0] * len(b)
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                cur[j] = prev[j - 1]
            else:
                cur[j] = 1 + min(prev[j], cur[j - 1], prev[j - 1])
        prev = cur
    return prev[-1]
```

## 3. Longest Palindromic Substring (LeetCode 5)

**🟠 Medium.** Return the longest palindromic substring of `s`.

```text
"babad" → "bab" (or "aba")
```

**Approach.** Expand around every centre: each index (odd length) and each gap between neighbours (even length). Grow while the characters on both sides match and keep the longest span.

**Complexity.** O(n²) time, O(1) space.

```typescript
function longestPalindrome(s: string): string {
  let bestL = 0, bestR = 0;
  const expand = (l: number, r: number): [number, number] => {
    while (l >= 0 && r < s.length && s[l] === s[r]) { l--; r++; }
    return [l + 1, r - 1];
  };
  for (let i = 0; i < s.length; i++) {
    for (const [l, r] of [expand(i, i), expand(i, i + 1)]) if (r - l > bestR - bestL) { bestL = l; bestR = r; }
  }
  return s.slice(bestL, bestR + 1);
}
```

```python
def longest_palindrome(s):
    best_l, best_r = 0, 0

    def expand(l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l, r = l - 1, r + 1
        return l + 1, r - 1                   # last valid span

    for i in range(len(s)):
        for l, r in (expand(i, i), expand(i, i + 1)):
            if r - l > best_r - best_l:
                best_l, best_r = l, r
    return s[best_l:best_r + 1]
```

## 4. Palindromic Substrings (LeetCode 647)

**🟠 Medium.** Count the palindromic substrings of `s` (different positions count separately).

```text
"aaa" → 6
```

**Approach.** Same centre expansion: every successful expansion step is one more palindrome.

**Complexity.** O(n²) time, O(1) space.

```typescript
function countSubstrings(s: string): number {
  let count = 0;
  for (let centre = 0; centre < 2 * s.length - 1; centre++) {
    let l = centre >> 1, r = l + (centre % 2);
    while (l >= 0 && r < s.length && s[l] === s[r]) { count++; l--; r++; }
  }
  return count;
}
```

```python
def count_substrings(s):
    count = 0
    for centre in range(2 * len(s) - 1):
        l = centre // 2
        r = l + centre % 2
        while l >= 0 and r < len(s) and s[l] == s[r]:
            count += 1
            l, r = l - 1, r + 1
    return count
```

## 5. Interleaving String (LeetCode 97)

**🟠 Medium.** Is `s3` formed by interleaving `s1` and `s2` (keeping each one's order)?

```text
"aabcc", "dbbca", "aadbbcbcac" → true
```

**Approach.** `dp[i][j]` = whether `s3[:i + j]` is an interleaving of `s1[:i]` and `s2[:j]`. It's true if the last character came from s1 (`dp[i−1][j]` and `s1[i−1] == s3[i+j−1]`) or from s2 (`dp[i][j−1]` and `s2[j−1] == s3[i+j−1]`).

**Complexity.** O(m · n) time, O(n) space.

```typescript
function isInterleave(s1: string, s2: string, s3: string): boolean {
  const m = s1.length, n = s2.length;
  if (m + n !== s3.length) return false;
  const dp = new Array(n + 1).fill(false);
  for (let i = 0; i <= m; i++) {
    for (let j = 0; j <= n; j++) {
      if (i === 0 && j === 0) { dp[0] = true; continue; }
      const fromS1 = i > 0 && dp[j] && s1[i - 1] === s3[i + j - 1];
      const fromS2 = j > 0 && dp[j - 1] && s2[j - 1] === s3[i + j - 1];
      dp[j] = fromS1 || fromS2;
    }
  }
  return dp[n];
}
```

```python
def is_interleave(s1, s2, s3):
    m, n = len(s1), len(s2)
    if m + n != len(s3):
        return False
    dp = [False] * (n + 1)
    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 and j == 0:
                dp[j] = True
                continue
            from_s1 = i > 0 and dp[j] and s1[i - 1] == s3[i + j - 1]
            from_s2 = j > 0 and dp[j - 1] and s2[j - 1] == s3[i + j - 1]
            dp[j] = from_s1 or from_s2
    return dp[n]
```

## 6. Regular Expression Matching (LeetCode 10)

**🔴 Hard.** Implement matching with `.` (any single character) and `*` (zero or more of the preceding element) over the whole string.

```text
"aab" matches "c*a*b" → true
```

**Approach.** `dp[i][j]` = whether `s[:i]` matches `p[:j]`. For `p[j−1] == '*'`: either use zero copies (`dp[i][j−2]`) or, if `s[i−1]` matches the element before `*`, consume one character (`dp[i−1][j]`). Otherwise the characters must match and `dp[i−1][j−1]` must hold.

**Complexity.** O(m · n) time and space.

```typescript
function isMatch(s: string, p: string): boolean {
  const m = s.length, n = p.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false));
  dp[0][0] = true;
  for (let j = 2; j <= n; j++) dp[0][j] = p[j - 1] === "*" && dp[0][j - 2];
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (p[j - 1] === "*") {
        dp[i][j] = dp[i][j - 2] || ((p[j - 2] === s[i - 1] || p[j - 2] === ".") && dp[i - 1][j]);
      } else {
        dp[i][j] = (p[j - 1] === s[i - 1] || p[j - 1] === ".") && dp[i - 1][j - 1];
      }
    }
  }
  return dp[m][n];
}
```

```python
def is_match(s, p):
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    for j in range(2, n + 1):                       # patterns like a*b* match ""
        dp[0][j] = p[j - 1] == "*" and dp[0][j - 2]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == "*":
                zero = dp[i][j - 2]
                one_more = p[j - 2] in (s[i - 1], ".") and dp[i - 1][j]
                dp[i][j] = zero or one_more
            else:
                dp[i][j] = p[j - 1] in (s[i - 1], ".") and dp[i - 1][j - 1]
    return dp[m][n]
```