String dynamic programming problems — longest common subsequence, edit distance, palindromic subsequences — appear frequently in senior engineering interviews. These problems share a 2D DP table structure where the state represents two substring positions.
Template: 2D String DP
Most string DP problems follow this template:
dp[i][j] = answer for s1[0..i-1] and s2[0..j-1] (first i chars of s1, j chars of s2)
Base cases: dp[0][j] = 0 (empty s1), dp[i][0] = 0 (empty s2)
Recurrence depends on whether s1[i-1] == s2[j-1]:
Case 1 (match): dp[i][j] = dp[i-1][j-1] + (some value)
Case 2 (no match): dp[i][j] = some combination of dp[i-1][j], dp[i][j-1], dp[i-1][j-1]Pattern 1: Longest Common Subsequence (LCS)
def lcs(s1: str, s2: str) -> int:
"""LC 1143: length of longest common subsequence"""
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 # extend LCS
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # skip one char
return dp[m][n] # Time O(mn), Space O(mn) → O(n) with rolling array
# Reconstruct the actual LCS:
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 to recover sequence
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))Pattern 2: Edit Distance (Levenshtein)
def minDistance(word1: str, word2: str) -> int:
"""LC 72: minimum operations (insert, delete, replace) to convert word1 → word2"""
m, n = len(word1), len(word2)
# dp[i][j] = edit distance between word1[:i] and word2[:j]
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Base cases: converting to/from empty string
for i in range(m + 1): dp[i][0] = i # delete all chars
for j in range(n + 1): dp[0][j] = j # insert all chars
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1] # no operation needed
else:
dp[i][j] = 1 + min(
dp[i-1][j], # delete from word1
dp[i][j-1], # insert into word1
dp[i-1][j-1] # replace
)
return dp[m][n]
# Space optimization to O(n):
def minDistance_optimized(word1, word2):
m, n = len(word1), len(word2)
prev = list(range(n + 1))
for i in range(1, m + 1):
curr = [i] + [0] * n
for j in range(1, n + 1):
if word1[i-1] == word2[j-1]:
curr[j] = prev[j-1]
else:
curr[j] = 1 + min(prev[j], curr[j-1], prev[j-1])
prev = curr
return prev[n]Pattern 3: Longest Palindromic Subsequence
def longestPalindromeSubseq(s: str) -> int:
"""LC 516: O(n²) — LPS = LCS(s, reverse(s))"""
return lcs(s, s[::-1])
# Direct DP solution:
def lps_direct(s: str) -> int:
n = len(s)
# dp[i][j] = LPS length in s[i..j]
dp = [[0] * n for _ in range(n)]
for i in range(n): dp[i][i] = 1 # single char is palindrome
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]Pattern 4: Longest Palindromic Substring
def longestPalindrome(s: str) -> str:
"""LC 5: O(n²) — expand around center"""
best_start = best_len = 0
def expand(left, right):
nonlocal best_start, best_len
while left >= 0 and right best_len:
best_start = left
best_len = right - left + 1
left -= 1; right += 1
for i in range(len(s)):
expand(i, i) # odd length
expand(i, i + 1) # even length
return s[best_start:best_start + best_len]
# DP approach O(n²) time and space:
def longestPalindrome_dp(s: str) -> str:
n = len(s)
dp = [[False] * n for _ in range(n)]
start = length = 0
for i in range(n): dp[i][i] = True
for i in range(n - 1):
if s[i] == s[i+1]:
dp[i][i+1] = True; start, length = i, 2
for l in range(3, n + 1):
for i in range(n - l + 1):
j = i + l - 1
if s[i] == s[j] and dp[i+1][j-1]:
dp[i][j] = True
if l > length: start, length = i, l
return s[start:start + length]Pattern 5: Minimum Insertions/Deletions for Palindrome
def minInsertions(s: str) -> int:
"""LC 1312: minimum insertions to make string palindrome"""
# Observation: LPS characters stay, rest need insertion for mirroring
# min_insertions = n - LPS_length
return len(s) - lps_direct(s)
def minOperationsToMakePalindrome(s: str) -> int:
"""Minimum deletions: n - LPS (delete non-palindromic chars)"""
n = len(s)
lps = lcs(s, s[::-1])
return n - lps # delete non-LPS charactersPattern 6: Shortest Common Supersequence (LC 1092)
def shortestCommonSupersequence(s1: str, s2: str) -> str:
"""Shortest string containing both s1 and s2 as subsequences"""
# Length: len(s1) + len(s2) - 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])
# Reconstruct: include LCS chars once, other chars from their string
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]:
result.append(s1[i-1]); i -= 1
else:
result.append(s2[j-1]); j -= 1
result.extend(reversed(s1[:i]))
result.extend(reversed(s2[:j]))
return ''.join(reversed(result))Pattern 7: Distinct Subsequences (LC 115)
def numDistinct(s: str, t: str) -> int:
"""Count distinct subsequences of s that equal t"""
m, n = len(s), len(t)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1): dp[i][0] = 1 # empty t: one way (take nothing)
for i in range(1, m + 1):
for j in range(1, n + 1):
dp[i][j] = dp[i-1][j] # skip s[i-1]
if s[i-1] == t[j-1]:
dp[i][j] += dp[i-1][j-1] # also use s[i-1] to match t[j-1]
return dp[m][n]String DP Problem Recognition
| Problem Type | DP State | Key Recurrence |
|---|---|---|
| LCS / common subsequence | dp[i][j] = length using s1[:i], s2[:j] | match: +1; no match: max(skip either) |
| Edit distance | dp[i][j] = min ops for s1[:i] → s2[:j] | match: 0; no match: 1+min(del,ins,rep) |
| Palindrome (subsequence) | dp[i][j] = LPS in s[i..j] | match: dp[i+1][j-1]+2; no: max(skip) |
| Count ways | dp[i][j] = number of ways | match: +previous; no match: carry forward |
Key Interview Tips
- Space optimization: Most string DP problems use only the current and previous rows. Replace the 2D table with two 1D arrays (prev, curr) for O(n) space. For single-string palindrome DP, the table is symmetric — compute the lower triangle only.
- LCS as a building block: Many string DP problems reduce to LCS. Palindrome = LCS(s, reverse(s)). Shortest common supersequence = len(s1)+len(s2)-LCS. Minimum deletions to make palindrome = len(s)-LCS(s, reverse(s)).
- Expand-around-center vs DP for palindromes: Expand-around-center is O(n²) time and O(1) space (no DP table) — prefer it for longest palindromic substring. DP is O(n²) time and O(n²) space — use when you need palindrome information for all sub-ranges (e.g., palindrome partitioning).
- Manacher’s algorithm: O(n) longest palindromic substring — rarely required in interviews but impressive to mention. The interviewable solution is expand-around-center.
Companies That Ask This
Asked at: Coinbase Interview Guide