Dynamic Programming on Strings — LCS, Edit Distance, and Palindromes

String DP problems look different from each other on the surface but they share one underlying structure: a 2D table where dp[i][j] represents some relationship between a prefix of one string and a prefix of another (or the same string). Once you see the grid, the recurrence writes itself.

Three patterns cover the vast majority of string DP interview questions. Master these, and everything else is a variation.

Pattern 1: Longest Common Subsequence (LCS)

Given two strings, find the length of their longest common subsequence. A subsequence doesn't need to be contiguous — you can skip characters.

"abcde" and "ace" → LCS = "ace", length 3

The Recurrence

dp[i][j] = LCS length of s1[0..i-1] and s2[0..j-1].

• If s1[i-1] == s2[j-1]: characters match, extend the LCS. dp[i][j] = dp[i-1][j-1] + 1
• Otherwise: skip one character from either string. dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Base case: dp[0][j] = dp[i][0] = 0 (empty string has LCS 0 with anything).

Python

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

return dp[m][n]

JavaScript

function lcs(s1, s2) {
  const m = s1.length, 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];
}

O(mn) time, O(mn) space. Space-optimizable to O(min(m,n)) since each row only depends on the previous row.

Reconstructing the LCS

Walk backward from dp[m][n]:

def lcs_string(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

# backtrack
    result = []
    i, j = m, n
    while i > 0 and j > 0:
        if s1[i - 1] == s2[j - 1]:
            result.append(s1[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

return ''.join(reversed(result))

LCS Variants

• Longest Common Substring (contiguous): reset to 0 when characters don't match instead of taking max. dp[i][j] = dp[i-1][j-1] + 1 if match, else 0. Track the global maximum.
• Shortest Common Supersequence: length = m + n - LCS(s1, s2). The supersequence includes both strings with shared parts merged.
• Minimum deletions to make strings equal: m + n - 2 * LCS(s1, s2).

Pattern 2: Edit Distance (Levenshtein Distance)

Given two strings, find the minimum number of operations (insert, delete, replace) to transform one into the other.

The Recurrence

dp[i][j] = edit distance between s1[0..i-1] and s2[0..j-1].

• If s1[i-1] == s2[j-1]: no operation needed. dp[i][j] = dp[i-1][j-1]
• Otherwise: take the minimum of three operations:

- Insert: dp[i][j-1] + 1 - Delete: dp[i-1][j] + 1 - Replace: dp[i-1][j-1] + 1

Base cases: dp[i][0] = i (delete all of s1), dp[0][j] = j (insert all of s2).

Python

def edit_distance(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i][j - 1],      # insert
                    dp[i - 1][j],      # delete
                    dp[i - 1][j - 1]   # replace
                )

return dp[m][n]

JavaScript

function editDistance(s1, s2) {
  const m = s1.length, n = s2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;

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];
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i][j - 1],
          dp[i - 1][j],
          dp[i - 1][j - 1]
        );
      }
    }
  }

return dp[m][n];
}

Edit Distance Variants

• Only insertions and deletions (no replace): dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1) when characters differ. Answer: m + n - 2 * LCS.
• One edit distance: are two strings exactly one edit apart? Special-case comparison, no DP needed.
• Regex matching / wildcard matching: different recurrence, same grid structure.

Pattern 3: Palindromic DP

These use a single string with dp[i][j] representing the substring from index i to j.

Longest Palindromic Subsequence

dp[i][j] = length of longest palindromic subsequence in s[i..j].

• If s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2
• Otherwise: dp[i][j] = max(dp[i+1][j], dp[i][j-1])
• Base: dp[i][i] = 1

def longest_palindrome_subseq(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]

for i in range(n):
        dp[i][i] = 1

for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

return dp[0][n - 1]

function longestPalindromeSubseq(s) {
  const n = s.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(0));

for (let i = 0; i < n; i++) dp[i][i] = 1;

for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      if (s[i] === s[j]) {
        dp[i][j] = dp[i + 1][j - 1] + 2;
      } else {
        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
      }
    }
  }

return dp[0][n - 1];
}

Key detail: iterate by length of substring, not by starting index. You need shorter substrings solved before longer ones.

Longest Palindromic Substring

Different from subsequence — this one requires contiguity. Expand around centers is O(n^2) and simpler. But the DP approach:

dp[i][j] = True if s[i..j] is a palindrome.

def longest_palindrome_substring(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    start, max_len = 0, 1

for i in range(n):
        dp[i][i] = True

for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                if length == 2 or dp[i + 1][j - 1]:
                    dp[i][j] = True
                    if length > max_len:
                        start, max_len = i, length

return s[start:start + max_len]

Minimum Insertions to Make Palindrome

Answer: n - LPS(s) where LPS is longest palindromic subsequence. The characters not in the LPS each need a matching insertion.

The Visualization That Makes It Click

For two-string problems (LCS, edit distance), draw the grid:

    ""  a  c  e
""   0  0  0  0
a    0  1  1  1
b    0  1  1  1
c    0  1  2  2
d    0  1  2  2
e    0  1  2  3

Each cell depends on its top, left, and top-left neighbors. That's it. The recurrence tells you which neighbor to use and how to combine them.

For single-string palindrome problems, the grid is lower-triangular (since i <= j), and you fill diagonals from the main diagonal outward.

Complexity Summary

Problem	Time	Space	Space-Optimized
LCS	O(mn)	O(mn)	O(min(m,n))
Edit Distance	O(mn)	O(mn)	O(min(m,n))
Longest Palindromic Subseq	O(n^2)	O(n^2)	O(n)
Longest Palindromic Substr	O(n^2)	O(n^2)	O(1) with expand

Common Mistakes

Off-by-one with 0-indexed vs 1-indexed. The DP table has dimensions (m+1) x (n+1) for two-string problems. dp[i][j] corresponds to s1[0..i-1] and s2[0..j-1], not s1[0..i]. Miss this and every cell is wrong. Iterating in the wrong order for palindromes. You must process shorter substrings before longer ones. Iterating by i from 0 to n doesn't guarantee this — iterate by length. Forgetting base cases. dp[i][0] and dp[0][j] for edit distance aren't 0 — they're i and j respectively. The cost of transforming a string to/from empty is the string's length. Confusing subsequence with substring. Subsequence: can skip characters, max operator when mismatch. Substring: must be contiguous, reset to 0 on mismatch.

These are probably the highest-frequency DP problems in interviews. Drill them on CodeUp until the 2D grid and recurrence feel automatic.