Dynamic Programming on Strings Pattern

When to use Dynamic Programming on Strings

• The problem compares two strings and asks for an edit distance, longest common substructure, or a count of matching pairs.
• The answer involves a single string but you need to consider every substring or every (i, j) prefix pair (palindromic subsequence, palindrome partitioning).
• Characters can be matched, inserted, deleted, or substituted, and each operation has a fixed cost or contribution.
• Brute-force recursion on (i, j) overlaps because the same prefix pair recurs through different match/skip orderings.
• The strings are short to medium (up to ~1000 characters) so an m * n table fits in memory.

Template

function stringDP(s1, s2) {
  const m = s1.length;
  const n = s2.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++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[m][n];
}

Common mistakes

• Indexing dp[i][j] by string indices instead of by prefix lengths, then forgetting to add the +1 offset that makes the empty-prefix base case fit cleanly.
• Off-by-one when reading s1[i - 1] vs s1[i] inside the loop body, producing answers shifted by one character.
• On Edit Distance, missing one of the three operations (insert, delete, substitute) in the recurrence, which gives a value larger than the true minimum.
• On Regular Expression Matching, treating the '*' as 'one or more' instead of 'zero or more of the preceding element' and mishandling the zero-occurrence case.
• Allocating an O(m * n) table when only the previous row is needed, blowing memory on long inputs.