Dynamic Programming on Strings Interview Patterns
String DP problems share a common structure: a 2D table where one dimension indexes into one string and the other indexes into a second string (or the same string in reverse). Once you internalize the table setup and base cases, these problems become mechanical.
Longest Common Subsequence (LC 1143)
Classic 2D DP. Recurrence: if characters match, dp[i][j] = dp[i-1][j-1] + 1; otherwise dp[i][j] = max(dp[i-1][j], dp[i][j-1]). The table is (m+1) x (n+1) to handle empty string base cases with zero-filled first row and column.
def longest_common_subsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[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]
# Space-optimized: O(n) space using rolling rows
def lcs_optimized(text1, text2):
m, n = len(text1), len(text2)
prev = [0] * (n + 1)
curr = [0] * (n + 1)
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
curr[j] = prev[j-1] + 1
else:
curr[j] = max(prev[j], curr[j-1])
prev, curr = curr, [0] * (n + 1)
return prev[n]
Edit Distance (LC 72)
Three operations: insert, delete, replace – each costs 1. When characters match, no operation needed: dp[i][j] = dp[i-1][j-1]. When they don’t match: dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) corresponding to replace, delete from s1, insert into s1.
def min_distance(word1, word2):
m, n = len(word1), len(word2)
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 from word1
for j in range(n + 1):
dp[0][j] = j # insert all chars of word2
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]
else:
dp[i][j] = 1 + min(
dp[i-1][j-1], # replace
dp[i-1][j], # delete from word1
dp[i][j-1] # insert into word1
)
return dp[m][n]
Longest Palindromic Subsequence (LC 516)
Two approaches. Approach 1: LCS of s and reversed(s) – elegant one-liner reduction. Approach 2: expand from single characters outward using a 2D DP table where dp[i][j] = longest palindromic subsequence in s[i..j].
# Approach 1: reduce to LCS
def longest_palindromic_subsequence(s):
return longest_common_subsequence(s, s[::-1])
# Approach 2: interval DP
def lps_interval(s):
n = len(s)
dp = [[0] * n for _ in range(n)]
# Base case: every single character is a palindrome of length 1
for i in range(n):
dp[i][i] = 1
# Fill by increasing interval length
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]
Palindrome Partitioning II (LC 132)
Two-phase DP. Phase 1: precompute a 2D boolean table is_palin[i][j] to answer palindrome queries in O(1). Phase 2: compute minimum cuts using cuts[i] = minimum cuts for s[0..i].
def min_cut(s):
n = len(s)
# Phase 1: precompute palindrome table
is_palin = [[False] * n for _ in range(n)]
for i in range(n):
is_palin[i][i] = True
for i in range(n - 1):
is_palin[i][i+1] = (s[i] == s[i+1])
for length in range(3, n + 1):
for i in range(n - length + 1):
j = i + length - 1
is_palin[i][j] = is_palin[i+1][j-1] and s[i] == s[j]
# Phase 2: minimum cuts
cuts = list(range(-1, n)) # cuts[i+1] = min cuts for s[0..i]
for i in range(n):
for j in range(i + 1):
if is_palin[j][i]:
cuts[i+1] = min(cuts[i+1], cuts[j] + 1)
return cuts[n]
Regular Expression Matching (LC 10)
Hard problem. Rules: ‘.’ matches any single character; ‘*’ matches zero or more of the preceding element. Build a 2D DP table where dp[i][j] means pattern p[0..j-1] matches string s[0..i-1]. The ‘*’ case is the tricky part: it either eliminates the preceding pattern char (use zero times) or consumes one char from s (use one or more times).
def is_match(s, p):
m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True # empty pattern matches empty string
# Handle patterns like a*, a*b*, a*b*c* matching empty string
for j in range(2, n + 1):
if p[j-1] == '*':
dp[0][j] = dp[0][j-2]
for i in range(1, m + 1):
for j in range(1, n + 1):
if p[j-1] == '*':
# Zero occurrences of preceding char: skip p[j-2] and p[j-1]
dp[i][j] = dp[i][j-2]
# One or more occurrences: preceding char must match s[i-1]
if p[j-2] == '.' or p[j-2] == s[i-1]:
dp[i][j] = dp[i][j] or dp[i-1][j]
elif p[j-1] == '.' or p[j-1] == s[i-1]:
dp[i][j] = dp[i-1][j-1]
return dp[m][n]
Distinct Subsequences (LC 115)
Count the number of ways to form target t as a subsequence of source s. dp[i][j] = number of ways to form t[0..i-1] from s[0..j-1]. If characters match, you can either use s[j-1] to match t[i-1] or skip it: dp[i][j] = dp[i-1][j-1] + dp[i][j-1]. If they don’t match, you must skip s[j-1]: dp[i][j] = dp[i][j-1].
def num_distinct(s, t):
m, n = len(t), len(s)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Base case: empty target can be formed in 1 way (use nothing)
for j in range(n + 1):
dp[0][j] = 1
for i in range(1, m + 1):
for j in range(1, n + 1):
dp[i][j] = dp[i][j-1] # skip s[j-1]
if t[i-1] == s[j-1]:
dp[i][j] += dp[i-1][j-1] # use s[j-1] to match t[i-1]
return dp[m][n]
Space Optimization: Rolling Two Rows
Most 2D string DP problems only look at the previous row to compute the current row. Rolling two arrays reduces space from O(m*n) to O(n). The LCS example above demonstrates this pattern. Apply it to edit distance and distinct subsequences the same way.
# Edit distance with O(n) space
def min_distance_optimized(word1, word2):
m, n = len(word1), len(word2)
prev = list(range(n + 1)) # base case: dp[0][j] = j
for i in range(1, m + 1):
curr = [i] + [0] * n # base case: dp[i][0] = i
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-1], prev[j], curr[j-1])
prev = curr
return prev[n]
Common Pitfalls
- 1-indexed vs 0-indexed offsets: when the DP table is (m+1) x (n+1), remember that
dp[i][j]corresponds tos[i-1]andt[j-1]. Mixing up the offset is the most common source of bugs. - Empty string base cases: always initialize the first row and column explicitly. Forgetting these leads to wrong answers on inputs where one string is empty.
- Interval DP fill order: for palindrome problems using interval DP, fill by increasing length, not by row. Getting the fill order wrong produces incorrect results silently.
- Rolling array diagonal: when rolling two rows, the diagonal value
dp[i-1][j-1]needs to be saved before being overwritten. Cache it in a variable at the start of each inner loop iteration.
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”How do you solve Longest Common Subsequence (LC 1143)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Build a 2D DP table where dp[i][j] = length of LCS of text1[0..i-1] and text2[0..j-1]. Base case: dp[0][j] = dp[i][0] = 0 (empty string has no common subsequence). Transition: if text1[i-1] == text2[j-1]: dp[i][j] = dp[i-1][j-1] + 1 (matching characters extend the LCS). Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (take the best without the current character from either string). Answer: dp[m][n]. Time O(m*n), space O(m*n). Space optimization: since dp[i] only depends on dp[i-1], use two rows, reducing space to O(min(m,n)). LCS is the base for edit distance, longest palindromic subsequence, and shortest common supersequence.”}},{“@type”:”Question”,”name”:”What is the recurrence for Edit Distance (LC 72)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Edit distance (Levenshtein distance) = minimum insertions, deletions, or substitutions to transform word1 into word2. dp[i][j] = edit distance between word1[0..i-1] and word2[0..j-1]. Base cases: dp[i][0] = i (delete all i chars), dp[0][j] = j (insert all j chars). Transition: 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-1], dp[i-1][j], dp[i][j-1]) where dp[i-1][j-1] = substitute, dp[i-1][j] = delete from word1, dp[i][j-1] = insert into word1. O(m*n) time and space. Space can be optimized to O(min(m,n)) with two rows. Applications: spell checkers, DNA sequence alignment, diff tools.”}},{“@type”:”Question”,”name”:”How do you solve Regular Expression Matching (LC 10)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”dp[i][j] = True if pattern[0..j-1] matches text[0..i-1]. Base: dp[0][0] = True. dp[0][j]: True if pattern[0..j-1] can match empty string (only possible if pattern[j-1] == '*' and dp[0][j-2] is True, i.e., the x* pattern matches zero occurrences). Transition: if pattern[j-1] == text[i-1] or pattern[j-1] == '.': dp[i][j] = dp[i-1][j-1] (characters match). If pattern[j-1] == '*': zero occurrences: dp[i][j] |= dp[i][j-2]. One or more occurrences: if pattern[j-2] matches text[i-1] (or pattern[j-2] == '.'): dp[i][j] |= dp[i-1][j]. The '*' case is the hardest – practice it until the transitions are automatic.”}},{“@type”:”Question”,”name”:”How do you find the minimum cuts for palindrome partitioning (LC 132)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Two-phase DP: (1) Precompute isPalin[i][j] = True if s[i..j] is a palindrome. Expand around center for each center position in O(n^2). (2) DP for minimum cuts: cuts[i] = minimum cuts for s[0..i]. Base: cuts[i] = i (worst case: cut before each char). For each j from 0 to i: if isPalin[j][i], then cuts[i] = min(cuts[i], 0 if j==0 else cuts[j-1]+1). Answer: cuts[n-1]. O(n^2) time, O(n^2) space for isPalin (can optimize to O(n) with careful implementation). The key insight: try every possible last palindrome partition s[j..i] and take the minimum.”}},{“@type”:”Question”,”name”:”How does Distinct Subsequences (LC 115) work?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Count the number of ways to form target as a subsequence of source. dp[i][j] = number of distinct subsequences of source[0..j-1] that equal target[0..i-1]. Base: dp[0][j] = 1 for all j (empty target is always a subsequence). dp[i][0] = 0 for i > 0 (non-empty target cannot be formed from empty source). Transition: dp[i][j] = dp[i][j-1] (always: do not use source[j-1]) + dp[i-1][j-1] if target[i-1] == source[j-1] (optionally use source[j-1] to match target[i-1]). The dp[i][j-1] term is "skip this source character." The dp[i-1][j-1] term is "use this source character to match the current target character." Answer: dp[m][n] where m = len(target), n = len(source).”}}]}
Meta coding interviews test string DP extensively. See common questions for Meta interview: string DP and dynamic programming problems.
Atlassian coding rounds include string DP and edit distance. See patterns for Atlassian interview: string algorithms and DP problems.
Apple coding rounds test string DP including LCS and edit distance. See patterns for Apple interview: string dynamic programming problems.