String DP

At a glance

The instinct

String DP comes in three shapes, and naming the shape first is most of the work:

1. Two strings, prefixes: dp[i][j] = answer for the first i characters of s and the first j characters of t. Each cell looks at the last characters s[i-1] and t[j-1] and decides: use both (diagonal), drop one from s (up), or drop one from t (left). LCS, Edit Distance, Wildcard Matching, Distinct Subsequences and Interleaving String all live here.
2. One string, ranges: dp[l][r] = answer for the substring s[l..r], built from shorter ranges inside it. Palindrome problems are the usual users.
3. One string, prefix splits: dp[i] = answer for the first i characters, by trying where the last piece starts (Word Break, Decode Ways, Palindrome Partitioning II).

Recognise it

Not this pattern if...

• Characters must be contiguous and the window just slides: longest substring without repeats is a sliding window.
• You search one exact pattern inside a text: KMP, Z-function or rolling hash.
• You must output all segmentations or partitions: that is backtracking (possibly with memo).

Memory hack

DP framing: state = dp[i][j] over prefix lengths (use an extra row/column for the empty prefix); choice = which of diagonal/up/left applies; base case = row 0 and column 0 (empty string versus a prefix); order = i ascending, j ascending. For range DP the order is by length, short ranges first.

Analogy: two people reading two scrolls side by side, each with a finger on their current letter. At every step they either both move a finger (letters agree, or one gets replaced) or only one moves (a letter is skipped, inserted or deleted). The table records the best outcome for every pair of finger positions.

Say it out loud in the interview:

1. "dp[i][j] means the answer for s[0..i) and t[0..j); row 0 / column 0 is the empty string."
2. "If the last characters match I take the diagonal; otherwise I combine up and left (and diagonal + 1 for replace)."
3. "Each row only reads the previous row, so I can drop to O(min(m, n)) space if asked."

How it works

Trace LCS for s = "abcde", t = "ace". Rows are prefixes of s, columns prefixes of t:

Bold cells are matches (diagonal + 1); every other cell copies the larger of up and left. The answer is the bottom-right cell, 3 ("ace").

Edit Distance uses the same grid with different rules: row 0 is j (insert j characters), column 0 is i (delete i characters), a match copies the diagonal, and a mismatch is 1 + min(diagonal, up, left) for replace, delete, insert.

For palindromes, dp[l][r] depends on dp[l+1][r-1] (shrink both ends), dp[l+1][r] and dp[l][r-1], so you loop l from right to left (or by increasing length) to make inner ranges ready first.

Java template

class TwoStringDP {
    // Prefix table template shown with Edit Distance; comments show the LCS swap.
    static int editDistance(String s, String t) {
        int m = s.length(), n = t.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) dp[i][0] = i;           // base: delete everything (LCS: 0)
        for (int j = 0; j <= n; j++) dp[0][j] = j;           // base: insert everything (LCS: 0)
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];             // LCS: diagonal + 1
                } else {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],    // replace
                               Math.min(dp[i - 1][j],            // delete from s
                                        dp[i][j - 1]));          // insert into s
                    // LCS: Math.max(dp[i - 1][j], dp[i][j - 1])
                }
            }
        }
        return dp[m][n];
    }
}

import java.util.*;

class OneStringDP {
    // Range DP: longest palindromic subsequence in s[l..r]. Fill l from right to left.
    static int longestPalSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int l = n - 1; l >= 0; l--) {
            dp[l][l] = 1;                                    // base: single character
            for (int r = l + 1; r < n; r++) {
                if (s.charAt(l) == s.charAt(r)) dp[l][r] = dp[l + 1][r - 1] + 2;
                else dp[l][r] = Math.max(dp[l + 1][r], dp[l][r - 1]);
            }
        }
        return n == 0 ? 0 : dp[0][n - 1];
    }

    // Prefix-split DP: can s be cut into dictionary words? dp[i] covers s[0..i).
    static boolean wordBreak(String s, List<String> words) {
        Set<String> dict = new HashSet<>(words);
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;                                        // empty prefix
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i && !dp[i]; j++) {          // j = where the last piece starts
                dp[i] = dp[j] && dict.contains(s.substring(j, i));
            }
        }
        return dp[n];
    }
}

Complexity

Variations

• Common subsequence family: Longest Common Subsequence; Delete Operation for Two Strings is m + n - 2·LCS; Shortest Common Supersequence is m + n - LCS.
• Edit family: Edit Distance - three operations map to the three arrows.
• Pattern matching: Wildcard Matching - * gives dp[i][j-1] || dp[i-1][j]; row 0 is true only while the pattern is all stars. Regular Expression Matching pairs * with the preceding character.
• Counting: Distinct Subsequences - on a match dp[i][j] = dp[i-1][j-1] + dp[i-1][j], otherwise dp[i-1][j]; use long or modulo.
• Interleaving: Interleaving String - dp[i][j] is true if the next character of s3 comes from s1 (up) or s2 (left).
• Palindromes: Longest Palindromic Subsequence (range DP), Longest Palindromic Substring and Palindromic Substrings (expand around 2n - 1 centres in O(n²) with O(1) space).
• Prefix splits: Word Break, Decode Ways (read one or two digits back; watch '0'), Palindrome Partitioning II (precompute isPal[l][r], then minimum cuts).

Common mistakes

• Missing base row/column. Edit Distance needs dp[i][0] = i and dp[0][j] = j; Wildcard Matching needs the leading-stars rule for row 0.
• Wrong fill order for range DP. Iterating l upward reads dp[l+1][...] before it exists; go from right to left or by length.
• Substring vs subsequence. Longest Palindromic Substring needs contiguous characters; using the subsequence recurrence gives too large an answer.
• Decode Ways zeros. "0" alone is invalid and "30" is not a letter; a single invalid step can make the whole count 0.
• Overflow in counting problems like Distinct Subsequences; use long or the stated modulo.

All practice problems

11 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.