Pattern Guide

String DP

"dp[i][j] = answer for s1[0..i-1] and s2[0..j-1]. Match or skip."

String DP builds a 2D table where dp[i][j] represents the best answer for substrings ending at positions i and j. Edit distance, LCS, shortest common supersequence, wildcard/regex matching, palindrome DP — all follow the same 2D table structure with 3-4 transition cases.

20 min readdp problems →

Problems you can solve with this pattern

6 problems · click any to start solving

All dp →

1Longest Common SubsequenceMediumSolve

2Edit DistanceMediumSolve

3Shortest Common SupersequenceHardSolve

4Interleaving StringMediumSolve

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

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]

Longest Common Subsequence

Medium

Solve

Edit Distance

Medium

Solve

Shortest Common Supersequence

Hard

Solve

Interleaving String

Medium

Solve

Longest Palindromic Subsequence

Medium

Solve

Wildcard Matching

Hard

Solve

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).

← Grid DP Knapsack DP →