DP on Strings: LCS, Edit Distance, Palindromes & Wildcard Matching

String DP has a reputation for being hard, and it is when every problem feels like a new puzzle. The secret is that it isn't a new puzzle each time. Across LCS, edit distance, distinct subsequences, interleaving strings, wildcard matching and the palindrome problems, there are essentially two state definitions and one way of reasoning about transitions. Once you've filled a couple of tables by hand, new problems become "which state, and what happens at the last character?"

This guide builds that up in order. First the two state shapes, then LCS in full detail (table, code, reconstruction, space optimisation), then the problems that are LCS in disguise, then edit distance, palindromes, and the matching problems that trip up most candidates. If DP in general still feels shaky, start with recursion for beginners, which covers the path from recursion to memoisation to tables.

The Two State Shapes for String DP

For shape 1, the reasoning step is always the same: look at the last character of each prefix, s[i−1] and t[j−1]. Either they match and can be used together, or you have to decide which one to drop (or edit). Each choice points to a smaller prefix pair: (i−1, j−1), (i−1, j) or (i, j−1), which are the diagonal, the cell above, and the cell to the left. Every recurrence below is a variation on that.

The extra row and column for empty prefixes are not an implementation detail. They're where the base cases live: "LCS of anything with an empty string is 0", "editing a 3-letter word into an empty string takes 3 deletions". Writing them down first makes the recurrence obviously correct at the edges.

Longest Common Subsequence (LeetCode 1143)

Given two strings, return the length of their longest common subsequence (characters in order, not necessarily contiguous).

• State: dp[i][j] = LCS length of s[:i] and t[:j].
• Base: dp[0][j] = dp[i][0] = 0.
• Transition: if s[i−1] == t[j−1], then dp[i][j] = dp[i−1][j−1] + 1. Otherwise dp[i][j] = max(dp[i−1][j], dp[i][j−1]).

Why is matching the last characters always safe? If both prefixes end in the same character, some LCS uses that pair: any LCS that doesn't could swap its last element for this pair without getting shorter. And on a mismatch, at least one of the two last characters isn't in the LCS, so dropping one or the other covers all cases.

Filled table for s = "abcde", t = "ace":

Bold cells are matches (diagonal + 1). The answer is the bottom-right cell, 3 ("ace").

def longestCommonSubsequence(s, t):
    m, n = len(s), len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

public int longestCommonSubsequence(String s, String t) {
    int m = s.length(), n = t.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = s.charAt(i - 1) == t.charAt(j - 1)
                     ? dp[i - 1][j - 1] + 1
                     : Math.max(dp[i - 1][j], dp[i][j - 1]);
    return dp[m][n];
}

O(m·n) time and space.

Reconstructing the LCS string

Interviewers often follow up with "print the subsequence". Walk back from dp[m][n]: on a match, take the character and go diagonal; otherwise move toward the larger neighbour.

def lcs_string(s, t, dp):
    i, j = len(s), len(t)
    out = []
    while i > 0 and j > 0:
        if s[i - 1] == t[j - 1]:
            out.append(s[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(out))

This needs the full table, which is the main reason not to space-optimise blindly. If both length and string are required with O(n) memory, Hirschberg's algorithm does it by divide and conquer; naming it is enough in most interviews.

Problems That Reduce to LCS (or Nearly)

A lot of string DP questions are LCS with a formula on top, or LCS with one line changed. Recognising this saves you from deriving a new recurrence under pressure.

Longest common substring: one line changes

def longest_common_substring(s, t):
    m, n = len(s), len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    best = 0
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                best = max(best, dp[i][j])
            # else: dp[i][j] stays 0, the contiguous run is broken
    return best

Here dp[i][j] means "length of the common substring ending exactly at s[i−1] and t[j−1]", which is a different state from LCS's "best over the whole prefixes". That's why the answer is the maximum cell, not the corner. Stating the state precisely is what keeps these two from blurring together.

Distinct Subsequences (LeetCode 115): counting instead of maximising

Count how many ways t appears as a subsequence of s. dp[i][j] = number of ways t[:j] appears in s[:i]. If s[i−1] == t[j−1], you can use this character for t's last character (dp[i−1][j−1] ways) or skip it (dp[i−1][j] ways); otherwise you must skip it.

public int numDistinct(String s, String t) {
    int m = s.length(), n = t.length();
    long[] dp = new long[n + 1];
    dp[0] = 1;                                  // empty t: one way (pick nothing)
    for (int i = 1; i <= m; i++)
        for (int j = Math.min(i, n); j >= 1; j--)   // right to left: dp[j-1] is still row i-1
            if (s.charAt(i - 1) == t.charAt(j - 1))
                dp[j] += dp[j - 1];
    return (int) dp[n];
}

Note the base case: one way to form the empty string, not zero. And the reverse loop over j, which lets one array stand in for two rows, the same trick 0/1 knapsack uses (see knapsack DP patterns).

Edit Distance (Levenshtein Distance, LeetCode 72)

Minimum number of single-character inserts, deletes and replaces to turn word1 into word2. This is the backbone of spell checkers and fuzzy search.

• State: dp[i][j] = edit distance between word1[:i] and word2[:j].
• Base: dp[i][0] = i (delete everything), dp[0][j] = j (insert everything).
• Match: if word1[i−1] == word2[j−1], dp[i][j] = dp[i−1][j−1] (no cost).
• Mismatch: dp[i][j] = 1 + min(dp[i−1][j−1] replace, dp[i−1][j] delete from word1, dp[i][j−1] insert into word1).

Filled table for "horse" → "ros":

Answer 3: replace h → r (rorse), delete r (rose), delete e (ros). Check one cell to make sure the recurrence clicks: at ("hor", "ro"), 'r' ≠ 'o', so it's 1 + min(diag ("ho","r") = 2, up ("ho","ro") = 1, left ("hor","r") = 2) = 2.

def minDistance(a, b):
    m, n = len(a), len(b)
    dp = list(range(n + 1))                   # row 0: j inserts
    for i in range(1, m + 1):
        diag = dp[0]                          # old dp[i-1][0]
        dp[0] = i                             # dp[i][0]: i deletes
        for j in range(1, n + 1):
            up = dp[j]                        # old dp[i-1][j]
            if a[i - 1] == b[j - 1]:
                dp[j] = diag
            else:
                dp[j] = 1 + min(diag, up, dp[j - 1])
            diag = up                         # becomes dp[i-1][j] for the next j
    return dp[n]

public int minDistance(String a, String b) {
    int m = a.length(), n = b.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1)
                     ? dp[i - 1][j - 1]
                     : 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
    return dp[m][n];
}

Follow-ups to prepare: One Edit Distance (161) is an O(n) two-pointer check, not DP; weighted edit costs just replace the 1s; and "return the actual edits" needs the full table plus a backtrack like LCS reconstruction. The LeetCode 72 walkthrough covers the memoised top-down version and these follow-ups.

Palindrome DP: Subsequences, Substrings and Partitions

Longest Palindromic Subsequence (LeetCode 516): interval DP

State shape 2. dp[i][j] = length of the longest palindromic subsequence in s[i..j].

• Base: dp[i][i] = 1.
• If s[i] == s[j]: dp[i][j] = dp[i+1][j−1] + 2 (both ends wrap the inner answer).
• Else: dp[i][j] = max(dp[i+1][j], dp[i][j−1]).

dp[i][j] depends on row i+1, so fill i from n−1 down to 0, and j from i+1 up.

def longestPalindromeSubseq(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        dp[i][i] = 1
        for j in range(i + 1, n):
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2      # for j == i+1 this reads 0: fine
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return dp[0][n - 1]

public int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    for (int i = n - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (int j = i + 1; j < n; j++)
            dp[i][j] = s.charAt(i) == s.charAt(j)
                     ? dp[i + 1][j - 1] + 2
                     : Math.max(dp[i + 1][j], dp[i][j - 1]);
    }
    return dp[0][n - 1];
}

For "bbbab" the answer is 4 ("bbbb"). When j = i+1 and the two characters match, dp[i+1][j−1] is dp[i+1][i], a cell below the diagonal that stays 0, so the formula correctly gives 2.

Longest Palindromic Substring (LeetCode 5): you don't need a table

A DP table works: is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j−1]. But it costs O(n²) space. The standard interview answer is expand around centre, O(n²) time and O(1) space: every palindrome has a centre, either a character or a gap between two characters, so try all 2n−1 centres.

def longestPalindrome(s):
    def expand(lo, hi):
        while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
            lo -= 1
            hi += 1
        return lo + 1, hi                     # s[lo+1:hi] is the palindrome

    best_lo, best_hi = 0, 0
    for c in range(len(s)):
        for lo, hi in (expand(c, c), expand(c, c + 1)):   # odd, even
            if hi - lo > best_hi - best_lo:
                best_lo, best_hi = lo, hi
    return s[best_lo:best_hi]

Manacher's algorithm does it in O(n), but it's rarely expected; mentioning it as a possible improvement is enough. Palindromic Substrings (647), which counts all palindromic substrings, is the same expansion with a counter.

Palindrome Partitioning II (LeetCode 132): minimum cuts

Combine the two ideas: precompute is_pal[i][j] (or expand around centres), then cuts[j] = minimum cuts for s[0..j] = 0 if s[0..j] is a palindrome, else min over i of cuts[i−1] + 1 where s[i..j] is a palindrome. O(n²) total. It shows how string DPs stack: one DP to answer "is this a palindrome", another that uses it as an O(1) oracle.

Wildcard Matching and Regular Expression Matching

These two are the hardest common string DPs, mostly because of how '*' behaves. Both use dp[i][j] = "does s[:i] match p[:j]?" with booleans.

Wildcard Matching (LeetCode 44)

'?' matches any single character; '*' matches any sequence, including empty.

• Base: dp[0][0] = true. dp[0][j] = dp[0][j−1] and p[j−1] == '*' (only leading stars can match an empty string). dp[i][0] = false for i > 0.
• If p[j−1] == '*': dp[i][j] = dp[i][j−1] (star matches empty) or dp[i−1][j] (star absorbs s[i−1] and stays available).
• If p[j−1] == '?' or equals s[i−1]: dp[i][j] = dp[i−1][j−1].

def isMatch(s, p):
    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):
        dp[0][j] = dp[0][j - 1] and p[j - 1] == '*'
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
            elif p[j - 1] == '?' or p[j - 1] == s[i - 1]:
                dp[i][j] = dp[i - 1][j - 1]
    return dp[m][n]

The "dp[i−1][j]" branch is the elegant part. Instead of trying every possible length for the star (which would add a loop and make it O(m²n)), the star consumes one character and remains in the pattern, so it can consume another on the next row.

Regular Expression Matching (LeetCode 10)

'.' matches any single character; '*' means zero or more of the preceding element. So "a*" is a unit, and the transition at a star looks two pattern characters back.

• Base: dp[0][0] = true. dp[0][j] = p[j−1] == '*' and dp[0][j−2] (patterns like "a*b*" match empty).
• If p[j−1] == '*': dp[i][j] = dp[i][j−2] (use "x*" zero times) or (s[i−1] matches p[j−2] and dp[i−1][j]) (use it once more).
• Else: dp[i][j] = s[i−1] matches p[j−1] and dp[i−1][j−1].

public boolean isMatch(String s, String p) {
    int m = s.length(), n = p.length();
    boolean[][] dp = new boolean[m + 1][n + 1];
    dp[0][0] = true;
    for (int j = 2; j <= n; j++)
        dp[0][j] = p.charAt(j - 1) == '*' && dp[0][j - 2];
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) {
            char pc = p.charAt(j - 1);
            if (pc == '*') {
                char prev = p.charAt(j - 2);           // valid input: '*' never first
                boolean oneMore = (prev == '.' || prev == s.charAt(i - 1)) && dp[i - 1][j];
                dp[i][j] = dp[i][j - 2] || oneMore;
            } else {
                dp[i][j] = (pc == '.' || pc == s.charAt(i - 1)) && dp[i - 1][j - 1];
            }
        }
    return dp[m][n];
}

def isMatchRegex(s, p):
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    for j in range(2, n + 1):
        dp[0][j] = p[j - 1] == '*' and dp[0][j - 2]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                one_more = p[j - 2] in ('.', s[i - 1]) and dp[i - 1][j]
                dp[i][j] = dp[i][j - 2] or one_more
            else:
                dp[i][j] = p[j - 1] in ('.', s[i - 1]) and dp[i - 1][j - 1]
    return dp[m][n]

Test cases worth running by hand: s = "aab", p = "c*a*b" is true ("c*" used zero times); s = "mississippi", p = "mis*is*p*." is false; s = "", p = "a*" is true. If your base row doesn't handle the third case, you'll fail on patterns that match the empty string.

Space Optimisation: From O(m·n) to O(n)

The rule: look at which cells a transition reads. Prefix DPs read (i−1, j−1), (i−1, j) and (i, j−1), so only the previous row and the current row matter.

1. Two rows: keep prev and cur, swap after each row. Easiest to get right.
2. One row + diagonal variable: before overwriting dp[j], save it; that saved value is the next iteration's diagonal. Used in the edit distance code above.
3. One row, reverse iteration: when a transition reads only (i−1, j) and (i−1, j−1), and never (i, j−1), iterate j from high to low so dp[j−1] still holds the old row. Used in Distinct Subsequences.
4. Use the shorter string for the row, giving O(min(m, n)).

Interval DPs (shape 2) also compress: dp[i][·] reads only dp[i+1][·] and itself, so one array iterated with i descending works for Longest Palindromic Subsequence. The cost of compression is reconstruction. Once old rows are gone, you can report the length or the boolean but not the actual alignment. Tell the interviewer this trade-off explicitly; it's one of the things they're checking.

How to Approach a String DP Problem in an Interview

A five-step script

1. Write the state in words. "dp[i][j] is the minimum edits to turn the first i chars of a into the first j chars of b." If you can't write this sentence, don't write code yet.
2. Write the base row and column. What's the answer when one string is empty?
3. Reason about the last characters. Match vs. mismatch; list each choice and the cell it points to.
4. Fill a 3×3 corner of the table by hand on the given example. This catches most recurrence bugs before coding.
5. State complexity, then offer the space optimisation and its reconstruction trade-off.

It's fine to start with a memoised recursive solution if that's how you think; many interviewers prefer it because it maps directly onto the reasoning. Convert to a table if asked about recursion depth or performance. The general DP version of this process is in dynamic programming interview questions.

What interviewers listen for

• A precise state definition before any code.
• A justification for the match case ("taking the matching pair is never worse").
• Correct handling of empty strings.
• Awareness that O(m·n) with m, n up to 10⁴ is 10⁸ cells; at that size, the 2D table is around 400 MB of ints, so space optimisation stops being optional.

String DP Problem List

Word Break is a one-string prefix DP rather than a two-string one, and it's worth doing alongside this list; the Word Break walkthrough covers it. Work through the table top to bottom and, for each problem, write the state sentence before anything else. By the end, regex matching should feel like a harder version of something you already know rather than a trick to memorise. For a different family of DP built on sequences rather than pairs of strings, continue with LIS patterns.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.