Pattern Reference
String DP
"DP on strings: edit distance, interleaving string, distinct subsequences, decode ways, regular expression."
Loading...
Deep Dive Tutorial
String DP problems compare or transform two strings (or a string with itself). The key structure: dp[i][j] = answer for s1[0..i-1] vs s2[0..j-1]. At each cell, you either match the current characters (use dp[i-1][j-1]) or skip from one side (use dp[i-1][j] or dp[i][j-1]). The exact formula depends on what you're optimizing.
The Three Fundamental Transitions
LCS, Edit Distance, and Shortest Common Supersequence templates
// All three use the same 2D dp structure:
// dp[i][j] = answer for s1[0..i-1] and s2[0..j-1]
// LCS (Longest Common Subsequence):
if (s1[i-1] === s2[j-1])
dp[i][j] = dp[i-1][j-1] + 1; // match: extend LCS
else
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); // skip one char from either
// Edit Distance (Levenshtein):
if (s1[i-1] === s2[j-1])
dp[i][j] = dp[i-1][j-1]; // match: no operation needed
else
dp[i][j] = 1 + Math.min(
dp[i-1][j-1], // replace s1[i-1] with s2[j-1]
dp[i-1][j], // delete s1[i-1]
dp[i][j-1] // insert s2[j-1] into s1
);
// Shortest Common Supersequence length:
if (s1[i-1] === s2[j-1])
dp[i][j] = dp[i-1][j-1] + 1; // use one char from both
else
dp[i][j] = 1 + Math.min(dp[i-1][j], dp[i][j-1]); // take one char from the shorter option| Problem | dp[i][j] meaning | Match case | Skip case |
|---|---|---|---|
| LCS | length of LCS of s1[0..i-1] and s2[0..j-1] | dp[i-1][j-1] + 1 | max(dp[i-1][j], dp[i][j-1]) |
| Edit Distance | min edits to convert s1[0..i-1] to s2[0..j-1] | dp[i-1][j-1] | min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1 |
| SCS length | length of shortest supersequence | dp[i-1][j-1] + 1 | min(dp[i-1][j], dp[i][j-1]) + 1 |
| Distinct subseqs | count of ways s2[0..j-1] appears in s1[0..i-1] | dp[i-1][j-1] + dp[i-1][j] | dp[i-1][j] |
Worked Problems
brain
String DP pattern guide:
- "Longest common subsequence" → LCS template (match or max-skip)
- "Min edits/operations" → Edit distance (match=free, otherwise min of 3 ops + 1)
- "Build supersequence" → LCS then reconstruct (merge two strings via LCS path)
- "Can s interleave s1 and s2?" → 2D boolean DP, one source at a time
- "Longest palindrome subsequence" → LCS(s, reverse(s)) or interval DP
- "Wildcard/regex matching" → 2D DP with special * handling
Space optimization: string DP only needs previous row → optimize from O(mn) to O(n).
- "Longest common subsequence" → LCS template (match or max-skip)
- "Min edits/operations" → Edit distance (match=free, otherwise min of 3 ops + 1)
- "Build supersequence" → LCS then reconstruct (merge two strings via LCS path)
- "Can s interleave s1 and s2?" → 2D boolean DP, one source at a time
- "Longest palindrome subsequence" → LCS(s, reverse(s)) or interval DP
- "Wildcard/regex matching" → 2D DP with special * handling
Space optimization: string DP only needs previous row → optimize from O(mn) to O(n).