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.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is the recurrence relation for Longest Common Subsequence (LCS) and how do you reconstruct the sequence?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “LCS recurrence: dp[i][j] = dp[i-1][j-1] + 1 if s1[i] == s2[j], else max(dp[i-1][j], dp[i][j-1]). The table is (m+1) u00d7 (n+1), initialized to 0. Fill row by row. The LCS length is dp[m][n]. To reconstruct: backtrack from dp[m][n] u2014 if s1[i] == s2[j], this character is in the LCS (add to result, move diagonally to dp[i-1][j-1]); else move in the direction of the larger neighbor (up or left). Reverse the collected characters for the actual subsequence. Time O(mu00d7n), space O(mu00d7n), reducible to O(min(m,n)) for just the length. LCS is the foundation for: edit distance (substitutions = LCS divergence), diff tools (git diff), and shortest common supersequence (length = m + n – LCS_length).”
}
},
{
“@type”: “Question”,
“name”: “How does the edit distance (Levenshtein) DP work and what are its interview applications?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Edit distance dp[i][j] = minimum operations to convert s1[:i] to s2[:j]. Base cases: dp[i][0] = i (delete i chars), dp[0][j] = j (insert j chars). Recurrence: if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] (no operation needed); else dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) for delete, insert, substitute respectively. O(mu00d7n) time and space, O(min(m,n)) with rolling array. Interview applications: (1) spell checking / autocorrect u2014 find the dictionary word with minimum edit distance; (2) DNA sequence alignment (bioinformatics); (3) fuzzy string matching u2014 “one edit away” check in O(n) by iterating through the DP just once. A useful optimization: if |m-n| > threshold, skip the full DP since distance u2265 |m-n|.”
}
},
{
“@type”: “Question”,
“name”: “How do you solve “Longest Palindromic Subsequence” and what is the relationship to LCS?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “The longest palindromic subsequence (LPS) of string s equals the LCS of s and its reverse reverse(s). Standalone DP: dp[i][j] = length of LPS in s[i..j]. Base case: dp[i][i] = 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]). Fill diagonally (increasing substring length). O(nu00b2) time and space, O(n) with rolling 1D array. The related problem “minimum insertions to make palindrome” = n – LPS_length: the characters NOT in the LPS need a mirror inserted. “Minimum deletions to make palindrome” = same formula. For finding ALL palindromic substrings (not subsequences), use expand-around-center in O(nu00b2) or Manacher’s algorithm in O(n).”
}
}
]
}