Dynamic Programming on Strings
String DP problems are among the most common in technical interviews, especially at Meta, Amazon, and Google. The unifying insight: when comparing two strings, define dp[i][j] as the answer for some prefix of s1 (length i) and some prefix of s2 (length j). The recurrence almost always branches on whether the current characters match.
The Two-String DP Template
# For problems comparing two strings s1 (len m) and s2 (len n):
# dp[i][j] = answer for s1[:i] and s2[:j]
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Base cases: dp[0][j] and dp[i][0] (empty string comparisons)
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
dp[i][j] = ... # use dp[i-1][j-1]
else:
dp[i][j] = ... # use dp[i-1][j], dp[i][j-1], dp[i-1][j-1]
Pattern 1: Longest Common Subsequence (LC 1143)
def longest_common_subsequence(s1: str, s2: str) -> int:
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 # characters match: extend LCS
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # skip one char from either
return dp[m][n]
Time O(m*n), Space O(m*n) — reducible to O(n) with rolling array. LCS is the foundation for diff tools (git diff), DNA sequence alignment, and plagiarism detection.
Pattern 2: Edit Distance (LC 72)
Minimum operations (insert, delete, replace) to transform s1 into s2.
def min_distance(s1: str, s2: str) -> int:
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Base cases: transforming empty string
for i in range(m + 1): dp[i][0] = i # delete all chars of s1
for j in range(n + 1): dp[0][j] = j # insert all chars of s2
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] # no operation needed
else:
dp[i][j] = 1 + min(
dp[i-1][j], # delete from s1
dp[i][j-1], # insert into s1
dp[i-1][j-1] # replace in s1
)
return dp[m][n]
Classic application: spell checkers (suggest words within edit distance 2), fuzzy search, bioinformatics.
Pattern 3: Longest Palindromic Subsequence (LC 516)
LCS of s and reverse(s). Or define dp[i][j] = LPS of s[i..j].
def longest_palindromic_subsequence(s: str) -> int:
# Method 1: LCS with reverse
return longest_common_subsequence(s, s[::-1])
def longest_palindromic_subsequence_v2(s: str) -> int:
# Method 2: Interval DP
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n): dp[i][i] = 1 # single char is palindrome of length 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]
Pattern 4: Distinct Subsequences (LC 115)
Count distinct ways s contains t as a subsequence.
def num_distinct(s: str, t: str) -> int:
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 is always a subsequence
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]: ways without this char
if s[i-1] == t[j-1]:
dp[i][j] += dp[i-1][j-1] # use s[i-1] to match t[j-1]
return dp[m][n]
Pattern 5: Shortest Common Supersequence (LC 1092)
Shortest string containing both s1 and s2 as subsequences. Length = m + n – LCS(s1, s2).
def shortest_common_supersequence(s1: str, s2: str) -> str:
# Build LCS dp table, then reconstruct supersequence
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: trace back dp table
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))
Space Optimization
All two-string DP tables can be reduced from O(m*n) to O(n) space using a rolling array — only the previous row is needed:
def lcs_space_optimized(s1, s2):
m, n = len(s1), len(s2)
prev = [0] * (n + 1)
for i in range(1, m + 1):
curr = [0] * (n + 1)
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
curr[j] = prev[j-1] + 1
else:
curr[j] = max(prev[j], curr[j-1])
prev = curr
return prev[n]
Interview Tips
- Always draw the dp table on a whiteboard with a small example — it makes the recurrence obvious.
- State the recurrence in English before coding: “dp[i][j] is the LCS of the first i chars of s1 and first j chars of s2.”
- Fill order matters: both i and j must increase left-to-right, top-to-bottom to use values from dp[i-1][…] and dp[…][j-1].
- Edit Distance vs LCS: they look similar but serve different purposes. Edit Distance counts operations; LCS counts matching characters.
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is the difference between Longest Common Subsequence and Edit Distance?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Both use a 2D DP table of size m*n and have the same structure, but they solve different problems. LCS (Longest Common Subsequence) counts the maximum number of characters that appear in both strings in the same order — it only allows skipping characters. When 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]). Edit Distance counts the minimum operations (insert, delete, replace) to transform s1 into s2. When characters match, dp[i][j] = dp[i-1][j-1] (no cost); else dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) for delete/insert/replace respectively. Relationship: for strings of length m and n, minimum edit distance using only insertions and deletions = m + n – 2*LCS(s1, s2).”}},{“@type”:”Question”,”name”:”How do you solve the Longest Palindromic Subsequence problem?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Two approaches: (1) Reduce to LCS — LPS(s) = LCS(s, reverse(s)). A palindromic subsequence must read the same forward and backward, so it must be a common subsequence of s and its reverse. This gives O(n²) time and O(n²) space. (2) Interval DP — define dp[i][j] = LPS of s[i..j]. Base case: dp[i][i] = 1 (single character). For 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]). Fill in order of increasing interval length (length 2, 3, …, n). Return dp[0][n-1]. The LCS approach is simpler to code; the interval DP approach is more generalizable to similar range problems. Both are O(n²) time and space.”}},{“@type”:”Question”,”name”:”What is the two-string DP template and how do you apply it?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”The two-string DP template: define dp[i][j] as the answer for s1[:i] (first i characters) and s2[:j] (first j characters). Initialize dp[0][j] and dp[i][0] as base cases (empty string). Fill with nested loops: for i in range(1, m+1): for j in range(1, n+1): if s1[i-1] == s2[j-1]: dp[i][j] = f(dp[i-1][j-1]); else: dp[i][j] = g(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]). This template solves LCS (f = +1, g = max), Edit Distance (f = copy, g = 1+min), Distinct Subsequences (f = dp[i-1][j-1] + dp[i-1][j], g = dp[i-1][j]), and Shortest Common Supersequence (same as LCS but reconstruct the string). Space can be reduced from O(mn) to O(n) using a rolling array — keep only the previous row since each cell only depends on the row above and the current row.”}}]}
🏢 Asked at: Meta Interview Guide 2026: Facebook, Instagram, WhatsApp Engineering
🏢 Asked at: Databricks Interview Guide 2026: Spark Internals, Delta Lake, and Lakehouse Architecture
🏢 Asked at: Apple Interview Guide 2026: iOS Systems, Hardware-Software Integration, and iCloud Architecture
🏢 Asked at: Atlassian Interview Guide
🏢 Asked at: Coinbase Interview Guide