String DP Patterns — Edit Distance, LCS, Interleaving, and Regex Matching
Sanjeev SharmaAdvertisement
Problem Statement
This guide covers the four canonical string DP problems and the unified pattern that links them:
- Edit Distance (Levenshtein) (LC 72) — minimum insertions, deletions, substitutions to transform
s1intos2. - Longest Common Subsequence (LC 1143) — length of the longest sequence appearing in
s1ands2in order, not necessarily contiguous. - Interleaving Strings (LC 97) — does
s3interleaves1ands2while preserving each one's order? - Regular Expression Matching (LC 10) — does pattern
p(with.and*) match stringsexactly?
Each defines a 2D table dp[i][j] indexed by prefixes of two strings. Each fills the table in O(nm) time and O(nm) or O(min(n, m)) space.
Why These Patterns Matter
String DP problems appear in roughly one in three FAANG interviews. Edit distance powers spell checkers, fuzzy search, DNA alignment, and version-control diffing. LCS underlies Unix diff, plagiarism detection, and merge tools. Interleaving validates parser ambiguity. Regex matching is the heart of every grep, sed, awk, lex, and editor find-and-replace.
Interviewers at Google, Meta, and Amazon use these problems to test three things at once: can you derive a recurrence, identify states, and optimise space? Each problem has a clean 2D recurrence and a well-known space-to-row optimisation. Botching the recurrence is fatal; muddling the space optimisation is forgivable but flagged.
The strategic value is leverage. Once you internalise the 2D-on-prefixes pattern, dozens of variants — distinct subsequences, longest palindromic subsequence, scramble strings, wildcard matching — become trivially adaptable. Each is a small tweak to one of the canonical four.
In production systems, edit distance is everywhere: typo correction in search, autocompletion, OCR confidence scoring, network protocol parsing. Knowing the algorithm separates "I know how to use Python's difflib" from "I can implement a domain-specific aligner."
The Core Insight
The unifying pattern: define dp[i][j] based on the first i characters of s1 and first j characters of s2 (or pattern). Walk the table from (0, 0) to (m, n) and the answer falls out of dp[m][n].
Edit Distance. dp[i][j] is the minimum operations to convert s1[0..i-1] to s2[0..j-1]. The recurrence:
dp[i][j] = dp[i-1][j-1] if s1[i-1] == s2[j-1] (no op)
= 1 + min(dp[i-1][j], (delete s1[i-1])
dp[i][j-1], (insert s2[j-1])
dp[i-1][j-1]) (substitute)Base cases: dp[i][0] = i (delete all i chars), dp[0][j] = j (insert all j chars).
LCS. dp[i][j] is the length of the longest common subsequence of s1[0..i-1] and s2[0..j-1]:
dp[i][j] = dp[i-1][j-1] + 1 if s1[i-1] == s2[j-1]
= max(dp[i-1][j], dp[i][j-1]) otherwiseThe "max from neighbours" branch is what allows non-contiguous matches.
Interleaving Strings. dp[i][j] is true if s3[0..i+j-1] is an interleaving of s1[0..i-1] and s2[0..j-1]:
dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1])
or (dp[i][j-1] and s2[j-1] == s3[i+j-1])Base case: dp[0][0] = True. The recurrence asks "did the last character come from s1 or s2?" and only allows transitions where the source character matches.
Regex Matching. dp[i][j] is true if s[0..i-1] matches p[0..j-1]:
If p[j-1] == '*':
dp[i][j] = dp[i][j-2] (zero occurrences)
or (dp[i-1][j] and (s[i-1] == p[j-2] or p[j-2] == '.'))
(one or more)
Else:
dp[i][j] = dp[i-1][j-1] and (s[i-1] == p[j-1] or p[j-1] == '.')The * case is the trickiest because * modifies the previous character; you must look two cells back.
The structural unity across the four: each dp[i][j] depends on dp[i-1][j], dp[i][j-1], and dp[i-1][j-1]. This means a row-by-row pass with two 1D arrays of size n+1 is enough — O(n) extra space instead of O(n*m).
Visual Dry Run — Edit Distance
s1 = "horse", s2 = "ros".
'' r o s
'' 0 1 2 3
h 1 1 2 3
o 2 2 1 2
r 3 2 2 2
s 4 3 3 2
e 5 4 4 3Trace dp[5][3]: minimum cost to convert "horse" to "ros" is 3.
dp[1][1]: convert"h"to"r"— substitute, cost 1.dp[2][2]: convert"ho"to"ro"— substitute h to r at position 0, no-op for o. Cost 1.dp[3][3]: convert"hor"to"ros"— delete h, no-op or, substitute r->s. Cost 2.dp[5][3]: convert"horse"to"ros"— delete h, no-op o, no-op r, delete s, delete e? Or h->r, delete o, no-op... Multiple paths give cost 3.
Reading off operations is more involved than reading the cost. Backtrack from (m, n) along the chosen branch to recover the edit script.
Solution (Optimal)
Python — Four Canonical String DPs
def edit_distance(s1: str, s2: str) -> int:
m, n = len(s1), len(s2)
dp = list(range(n + 1))
for i in range(1, m + 1):
prev_diag = dp[0]
dp[0] = i
for j in range(1, n + 1):
tmp = dp[j]
if s1[i - 1] == s2[j - 1]:
dp[j] = prev_diag
else:
dp[j] = 1 + min(dp[j], dp[j - 1], prev_diag)
prev_diag = tmp
return dp[n]
def lcs(s1: str, s2: str) -> int:
m, n = len(s1), len(s2)
dp = [0] * (n + 1)
for i in range(1, m + 1):
prev_diag = 0
for j in range(1, n + 1):
tmp = dp[j]
if s1[i - 1] == s2[j - 1]:
dp[j] = prev_diag + 1
else:
dp[j] = max(dp[j], dp[j - 1])
prev_diag = tmp
return dp[n]
def is_interleave(s1: str, s2: str, s3: str) -> bool:
m, n = len(s1), len(s2)
if m + n != len(s3):
return False
dp = [False] * (n + 1)
dp[0] = True
for j in range(1, n + 1):
dp[j] = dp[j - 1] and s2[j - 1] == s3[j - 1]
for i in range(1, m + 1):
dp[0] = dp[0] and s1[i - 1] == s3[i - 1]
for j in range(1, n + 1):
dp[j] = ((dp[j] and s1[i - 1] == s3[i + j - 1])
or (dp[j - 1] and s2[j - 1] == s3[i + j - 1]))
return dp[n]
def is_match(s: str, p: str) -> bool:
m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for j in range(1, 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] == '*':
dp[i][j] = dp[i][j - 2]
if p[j - 2] == '.' or p[j - 2] == s[i - 1]:
dp[i][j] = dp[i][j] or dp[i - 1][j]
else:
dp[i][j] = (dp[i - 1][j - 1] and
(p[j - 1] == '.' or p[j - 1] == s[i - 1]))
return dp[m][n]JavaScript — Edit Distance and LCS
function editDistance(s1, s2) {
const m = s1.length, n = s2.length;
let dp = Array.from({ length: n + 1 }, (_, j) => j);
for (let i = 1; i <= m; i++) {
let prevDiag = dp[0];
dp[0] = i;
for (let j = 1; j <= n; j++) {
const tmp = dp[j];
if (s1[i - 1] === s2[j - 1]) {
dp[j] = prevDiag;
} else {
dp[j] = 1 + Math.min(dp[j], dp[j - 1], prevDiag);
}
prevDiag = tmp;
}
}
return dp[n];
}
function lcs(s1, s2) {
const m = s1.length, n = s2.length;
const dp = new Array(n + 1).fill(0);
for (let i = 1; i <= m; i++) {
let prevDiag = 0;
for (let j = 1; j <= n; j++) {
const tmp = dp[j];
if (s1[i - 1] === s2[j - 1]) dp[j] = prevDiag + 1;
else dp[j] = Math.max(dp[j], dp[j - 1]);
prevDiag = tmp;
}
}
return dp[n];
}Complexity: O(n*m) time, O(min(n, m)) space when collapsed to a single rolling row plus a prev_diag scalar.
Common Mistakes
Mishandling base cases. dp[0][j] = j for edit distance, dp[0][j] = 0 for LCS. The wrong base seeds incorrect values throughout. Always pencil out the first row and column before coding.
Using the wrong recurrence for substring vs subsequence. Edit distance and LCS look similar but differ in the mismatch branch. Substring resets to zero (covered in part 7); subsequence takes max from neighbours.
Forgetting dp[i][j-2] in regex *. The * modifies the previous pattern character, so zero occurrences means jumping back two cells, not one. Easy to write dp[i][j-1] and pass small tests but fail on s = "aab", p = "c*a*b".
Not handling the regex empty pattern row correctly. When s = "", only patterns of the form x*y*z*... match. Initialise the empty-string row with the explicit dp[0][j] = dp[0][j-2] when p[j-1] == '*'.
Premature space optimisation. Collapsing to one row before the recurrence is solid causes hours of debugging. Get the 2D version right first, then optimise.
Off-by-one with prev_diag. When using a single rolling row, the diagonal predecessor is the value of dp[j] before it was updated this iteration. Save it in tmp before the assignment.
Interview Tips
State the state and recurrence before writing code. "Let dp[i][j] be ... and the recurrence is ..." is the universal opening that earns trust.
Draw the small table by hand. Interviewers love watching candidates fill in the first few cells; it reveals whether you understand the recurrence or are pattern-matching.
After the 2D version works, mention space optimisation. Say "We can collapse to two 1D arrays of size n+1 because each cell only depends on the previous row and current row." For credit, implement the optimisation; for partial credit, just state it.
For follow-up questions about reconstructing the edit script, mention that you store the table and backtrack from (m, n). Each cell records which branch was taken; the path from (m, n) to (0, 0) enumerates the operations in reverse.
For wildcard matching (LC 44 with ? and * where * matches any sequence), the recurrence is similar but simpler: * extends by either consuming a character (dp[i-1][j]) or skipping itself (dp[i][j-1]). Mention this as a sister problem.
For the LCS variant that returns the actual subsequence, build the table O(n*m) and backtrack from (m, n) taking the diagonal when characters match and the larger of up/left otherwise.
Follow-up Questions
Q: How do you reduce edit distance space to O(min(n, m))?
A: Iterate over the smaller dimension. Maintain one rolling row of size min(n, m) + 1 plus a scalar prev_diag. Each cell update overwrites in place, with the diagonal predecessor saved before the overwrite.
Q: What is the Hunt-Szymanski algorithm and why does it matter for LCS?
A: It is an O((n + r) log n) algorithm where r is the number of matching position pairs. For long files with few common lines (typical in diff), r is much less than n*m, giving near-linear performance. Used in production diff tools.
Q: How do you support transpositions in edit distance?
A: The Damerau-Levenshtein distance adds a fourth case: dp[i][j] = min(..., dp[i-2][j-2] + 1) if s1[i-1] == s2[j-2] and s1[i-2] == s2[j-1]. Useful for typo detection where adjacent transpositions are common.
Q: How does the Hirschberg algorithm reduce LCS to linear space?
A: Divide and conquer: split s1 in half, find the optimal split point in s2 using two forward passes (O(m) space), then recurse on the two halves. Total space O(min(n, m)), time still O(n*m).
Q: How do you adapt regex matching to support backreferences?
A: Backreferences (\1, \2) make the language context-sensitive — pure regex DP no longer suffices. The standard approach is backtracking with memoisation, exponential worst case. This is why production regex engines like RE2 deliberately exclude backreferences.
Key Takeaways
- The four canonical string DP problems all index by prefixes:
dp[i][j]overs1[0..i-1]ands2[0..j-1](orp[0..j-1]). - Edit distance uses substitution, insertion, deletion costs; LCS uses match-or-skip; interleaving uses source-of-last-character; regex uses pattern-character-with-special-cases.
- All four collapse to O(n*m) time and O(min(n, m)) space using a rolling row and a
prev_diagscalar. - Regex matching's
*case requires looking two cells back because*modifies the previous character; this is the most common source of bugs. - Mastering this family of recurrences unlocks dozens of variants — distinct subsequences, palindromic subsequences, scramble strings, wildcard matching — with minor tweaks.
- Interview signal: stating the recurrence cleanly, walking a small table by hand, and optimising space demonstrates the full DP toolkit FAANG values.
Advertisement
