Engineering Notes
Home/Algorithms & Coding Interviews/Greedy, DP & Bits/DP on Strings
Algorithms & Coding Interviews · Greedy, DP & Bits

DP on Strings

String DP comes in two shapes: two-string prefix tables (LCS, edit distance, interleaving, regex) and single-string intervals (palindromes). Learn how to read the diagonal, up and left neighbours, the empty-prefix base row, centre expansion, and watch LCS, Edit Distance and palindrome expansion animated.

🧮 Algorithms & Coding Interviews● Advanced⏱ 11 min read▶ 3 interactive🛠️ 4 exercises

🎯 What you'll learn

  • Two-string prefix tables and their base row/column
  • What each neighbour means in LCS vs edit distance
  • Palindromes: centre expansion vs interval DP
  • Six LeetCode problems up to Regular Expression Matching

📚 Before you start

Part 1The 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
LCS table: matches extend the diagonal, mismatches take the better neighbour

1Two-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.

2Reading the Neighbours

Move into dp[i][j] fromMeaning in LCSMeaning in edit distance
diagonal dp[i−1][j−1]characters match: extend by 1match (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)

3Palindromes: 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.)

4Subsequence 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 HoodWhere 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
Part 2Interview Problems

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

1Longest 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]

2Edit 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]

3Longest 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]

4Palindromic 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

5Interleaving 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]

6Regular 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]

🧠 Key takeaways

  • Two strings → dp[i][j] over prefixes, with an empty-prefix row and column.
  • Diagonal = use both characters; up/left = skip (LCS) or delete/insert (edit distance).
  • Palindromes: expand around 2n − 1 centres in O(n²) time and O(1) space.
  • Know substring vs subsequence; roll rows to cut space to O(n).

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

#1
algo_dp_on_strings_exercise_1.py
TSPY
#2
algo_dp_on_strings_exercise_2.py
TSPY

✅ Check yourself

Answer the questions — feedback is instant.

1. In edit distance, moving from dp[i-1][j] to dp[i][j] means…
One fewer character of a.
2. Base value dp[i][0] for edit distance:
Delete all i characters.
3. How many centres are there for palindrome expansion in a string of length n?
Characters and gaps.
4. Longest palindromic subsequence equals…
A classic reduction.

Source: algo_dp_on_strings_theory_1.md, algo_dp_on_strings_theory_2.md · generated by tools/build_lessons.py