Autocoder

Edit Distance and String DP Interview Questions

Last updated 2026-11-19

String dynamic programming covers problems where decisions are made character by character: how many edits turn one word into another, whether a pattern matches, how to split a string into palindromes. Edit distance is the headline example, and the same table shape underlies many follow-ups.

The problems here run from the one-edit check to regular expression matching, each with Python and Java code, complexity and edge cases. For the closest relative of edit distance see longest common subsequence interview questions. Basic string handling is covered in string interview questions.

Edit distanceO(m * n) time, O(n) space
Matching problemsdp[i][j] over prefixes of text and pattern
PalindromesExpand around centres, O(n^2)
OperationsInsert, delete, replace

The pattern and when to spot it

If two strings are being transformed or matched, define dp[i][j] over prefixes of both and decide what the last characters allow. For edit distance the options are replace, delete or insert. For wildcard and regular expressions, the pattern character decides: a star offers a choice between consuming nothing and consuming one more character, while a dot or question mark behaves as any single letter.

When one string is processed alone, as in palindrome problems, the state is a pair of positions or a single prefix. Centre expansion finds all palindromic substrings in O(n^2) without a table. A palindrome table plus a cut array gives partition problems. For prefix and border questions, such as the shortest palindrome, the KMP failure function replaces a quadratic search with one linear pass.

Mistakes to avoid

Edit Distance and String DP Interview Questions: questions with worked answers

  1. 1

    One edit distance: are two strings exactly one edit apart?

    easy

    Compare lengths first: they may differ by at most 1. Find the first mismatching position. If lengths are equal, the rest after the mismatch must match (a replace). If they differ, skip one character in the longer string and the rest must match (an insert or delete). With no mismatch, the strings are one edit apart only if the lengths differ by exactly 1. Time O(n), space O(1). Edge cases: identical strings (false, zero edits), lengths differing by 2 or more, mismatch at the last character, empty string versus one character.

    python
    def is_one_edit(s, t):
        if abs(len(s) - len(t)) > 1:
            return False
        if len(s) > len(t):
            s, t = t, s
        for i in range(len(s)):
            if s[i] != t[i]:
                return s[i+1:] == t[i+1:] if len(s) == len(t) else s[i:] == t[i+1:]
        return len(t) - len(s) == 1
    java
    boolean isOneEdit(String s, String t) {
        if (Math.abs(s.length() - t.length()) > 1) return false;
        if (s.length() > t.length()) { String x = s; s = t; t = x; }
        for (int i = 0; i < s.length(); i++)
            if (s.charAt(i) != t.charAt(i))
                return s.length() == t.length() ? s.substring(i + 1).equals(t.substring(i + 1))
                                               : s.substring(i).equals(t.substring(i + 1));
        return t.length() - s.length() == 1;
    }
  2. 2

    Edit distance (Levenshtein)

    medium

    dp[i][j] is the fewest edits to turn the first i characters of a into the first j of b. If the characters match, copy dp[i-1][j-1]. Otherwise take 1 plus the best of replace (dp[i-1][j-1]), delete (dp[i-1][j]) and insert (dp[i][j-1]). The first row and column are the costs of building from or deleting to empty. Time O(m * n), space O(n) with a rolling row. Edge cases: either string empty (length of the other), identical strings (0), all three operations costing 1 (change the recurrence for weighted costs).

    python
    def edit_distance(a, b):
        prev = list(range(len(b) + 1))
        for i, x in enumerate(a, 1):
            cur = [i]
            for j, y in enumerate(b, 1):
                if x == y:
                    cur.append(prev[j - 1])
                else:
                    cur.append(1 + min(prev[j - 1], prev[j], cur[j - 1]))
            prev = cur
        return prev[-1]
    java
    int editDistance(String a, String b) {
        int[] prev = new int[b.length() + 1];
        for (int j = 0; j <= b.length(); j++) prev[j] = j;
        for (int i = 1; i <= a.length(); i++) {
            int[] cur = new int[b.length() + 1];
            cur[0] = i;
            for (int j = 1; j <= b.length(); j++)
                cur[j] = a.charAt(i-1) == b.charAt(j-1) ? prev[j-1]
                       : 1 + Math.min(prev[j-1], Math.min(prev[j], cur[j-1]));
            prev = cur;
        }
        return prev[b.length()];
    }
  3. 3

    List the actual edit operations

    medium

    Keep the full table and walk back from dp[m][n]. If characters match and dp[i][j] equals dp[i-1][j-1], no operation is needed. Otherwise find which neighbour produced dp[i][j] - 1: diagonal means replace, up means delete, left means insert. Collect operations and reverse them. Time O(m * n), space O(m * n). Edge cases: several optimal scripts (any is valid), equal strings produce an empty script, order of checks decides which script is returned.

    python
    def edit_script(a, b):
        m, n = len(a), len(b)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1): dp[i][0] = i
        for j in range(n + 1): dp[0][j] = j
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                dp[i][j] = dp[i-1][j-1] if a[i-1] == b[j-1] else 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
        ops, i, j = [], m, n
        while i or j:
            if i and j and a[i-1] == b[j-1] and dp[i][j] == dp[i-1][j-1]:
                i -= 1; j -= 1
            elif i and j and dp[i][j] == dp[i-1][j-1] + 1:
                ops.append(f"replace {a[i-1]} with {b[j-1]}"); i -= 1; j -= 1
            elif i and dp[i][j] == dp[i-1][j] + 1:
                ops.append(f"delete {a[i-1]}"); i -= 1
            else:
                ops.append(f"insert {b[j-1]}"); j -= 1
        return ops[::-1]
    java
    List<String> editScript(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]));
        LinkedList<String> ops = new LinkedList<>();
        int i = m, j = n;
        while (i > 0 || j > 0) {
            if (i > 0 && j > 0 && a.charAt(i-1) == b.charAt(j-1) && dp[i][j] == dp[i-1][j-1]) { i--; j--; }
            else if (i > 0 && j > 0 && dp[i][j] == dp[i-1][j-1] + 1) { ops.addFirst("replace " + a.charAt(i-1) + " with " + b.charAt(j-1)); i--; j--; }
            else if (i > 0 && dp[i][j] == dp[i-1][j] + 1) { ops.addFirst("delete " + a.charAt(i-1)); i--; }
            else { ops.addFirst("insert " + b.charAt(j-1)); j--; }
        }
        return ops;
    }
  4. 4

    Count palindromic substrings

    medium

    Every palindrome has a centre: a character or a gap between two characters. For each of the 2n - 1 centres expand outwards while the ends match, and count each successful expansion. Distinct positions count separately even if the text is the same. Time O(n^2), space O(1). Edge cases: single character (1), all identical characters (n(n+1)/2), no repeats (n), empty string.

    python
    def count_substrings(s):
        count = 0
        for c in range(2 * len(s) - 1):
            l, r = c // 2, c // 2 + c % 2
            while l >= 0 and r < len(s) and s[l] == s[r]:
                count += 1
                l -= 1
                r += 1
        return count
    java
    int countSubstrings(String s) {
        int count = 0;
        for (int c = 0; c < 2 * s.length() - 1; c++) {
            int l = c / 2, r = l + c % 2;
            while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { count++; l--; r++; }
        }
        return count;
    }
  5. 5

    Palindrome partitioning II: minimum cuts

    hard

    Precompute pal[i][j], whether s[i..j] is a palindrome, by expanding around centres. Then cuts[j] is the fewest cuts for the prefix ending at j: zero if the whole prefix is a palindrome, otherwise the minimum of cuts[i-1] + 1 over i where s[i..j] is a palindrome. Time O(n^2), space O(n^2). Edge cases: already a palindrome (0), no equal adjacent letters (n - 1 cuts), single character, empty string.

    python
    def min_cut(s):
        n = len(s)
        if n == 0:
            return 0
        pal = [[False] * n for _ in range(n)]
        for c in range(2 * n - 1):
            l, r = c // 2, c // 2 + c % 2
            while l >= 0 and r < n and s[l] == s[r]:
                pal[l][r] = True
                l -= 1; r += 1
        cuts = [0] * n
        for j in range(n):
            if pal[0][j]:
                cuts[j] = 0
            else:
                cuts[j] = min(cuts[i - 1] + 1 for i in range(1, j + 1) if pal[i][j])
        return cuts[n - 1]
    java
    int minCut(String s) {
        int n = s.length();
        if (n == 0) return 0;
        boolean[][] pal = new boolean[n][n];
        for (int c = 0; c < 2 * n - 1; c++) {
            int l = c / 2, r = l + c % 2;
            while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) { pal[l][r] = true; l--; r++; }
        }
        int[] cuts = new int[n];
        for (int j = 0; j < n; j++) {
            if (pal[0][j]) { cuts[j] = 0; continue; }
            cuts[j] = Integer.MAX_VALUE;
            for (int i = 1; i <= j; i++) if (pal[i][j]) cuts[j] = Math.min(cuts[j], cuts[i - 1] + 1);
        }
        return cuts[n - 1];
    }
  6. 6

    Longest valid parentheses

    hard

    Let dp[i] be the length of the longest valid substring ending at i; it is nonzero only when s[i] is a closing bracket. If s[i-1] is an opening bracket, dp[i] = dp[i-2] + 2. Otherwise, if the character just before the valid block ending at i-1 is an opening bracket, dp[i] = dp[i-1] + 2 + dp[index before that bracket]. The answer is the maximum entry. Time O(n), space O(n). Edge cases: empty string (0), strings starting with a closing bracket, adjacent valid blocks that must be concatenated, deeply nested valid strings.

    python
    def longest_valid(s):
        n = len(s)
        dp = [0] * n
        best = 0
        for i in range(1, n):
            if s[i] == ')':
                if s[i - 1] == '(':
                    dp[i] = (dp[i - 2] if i >= 2 else 0) + 2
                else:
                    j = i - dp[i - 1] - 1
                    if j >= 0 and s[j] == '(':
                        dp[i] = dp[i - 1] + 2 + (dp[j - 1] if j >= 1 else 0)
                best = max(best, dp[i])
        return best
    java
    int longestValid(String s) {
        int n = s.length(), best = 0;
        int[] dp = new int[n];
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) != ')') continue;
            if (s.charAt(i - 1) == '(') dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
            else {
                int j = i - dp[i - 1] - 1;
                if (j >= 0 && s.charAt(j) == '(') dp[i] = dp[i - 1] + 2 + (j >= 1 ? dp[j - 1] : 0);
            }
            best = Math.max(best, dp[i]);
        }
        return best;
    }
  7. 7

    Wildcard matching with ? and *

    hard

    dp[i][j] is true if the first i characters of s match the first j of the pattern. A star can match an empty sequence (dp[i][j-1]) or consume one more character (dp[i-1][j]). A question mark or an equal letter needs dp[i-1][j-1]. A leading run of stars matches the empty string, so initialise dp[0][j] accordingly. Time O(m * n), space O(m * n). Edge cases: pattern of only stars (matches anything including empty), empty string with a non-star pattern, consecutive stars, a star at the end.

    python
    def is_match(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]
    java
    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 = 1; j <= n; j++) dp[0][j] = dp[0][j - 1] && p.charAt(j - 1) == '*';
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++) {
                char c = p.charAt(j - 1);
                if (c == '*') dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                else if (c == '?' || c == s.charAt(i - 1)) dp[i][j] = dp[i - 1][j - 1];
            }
        return dp[m][n];
    }
  8. 8

    Regular expression matching with . and *

    hard

    Here a star applies to the previous element: zero or more of it. dp[i][j] for the first i characters of s and j of p. If p[j-1] is a star, either skip the pair x* (dp[i][j-2]) or, when the previous pattern character matches s[i-1], consume one character (dp[i-1][j]). Otherwise, a dot or a letter match needs dp[i-1][j-1]. Time O(m * n), space O(m * n). Edge cases: patterns such as a*b* matching the empty string, a star that cannot be first, dot-star matching anything, star meaning zero occurrences.

    python
    def is_regex_match(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] == '*':
                    dp[i][j] = dp[i][j - 2] or (
                        j >= 2 and (p[j - 2] == '.' or p[j - 2] == s[i - 1]) and 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]
    java
    boolean isRegexMatch(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 c = p.charAt(j - 1);
                if (c == '*') {
                    dp[i][j] = dp[i][j - 2]
                        || (j >= 2 && (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) && dp[i - 1][j]);
                } else if (c == '.' || c == s.charAt(i - 1)) dp[i][j] = dp[i - 1][j - 1];
            }
        return dp[m][n];
    }
  9. 9

    Minimum cost to convert one string into another with letter conversion rules

    medium

    Each rule says letter x can become y at some cost. Conversions can chain, so compute the cheapest cost between every pair of the 26 letters with Floyd-Warshall, taking the minimum over parallel rules. Then sum the cost for each position where source and target differ, and return -1 if any pair is unreachable. Time O(26^3 + n + rules), space O(26^2). Edge cases: same letters cost 0, unreachable pair (-1), multiple rules for the same pair (keep the cheapest), long totals needing long.

    python
    def minimum_cost(source, target, original, changed, cost):
        INF = float('inf')
        d = [[0 if i == j else INF for j in range(26)] for i in range(26)]
        for x, y, c in zip(original, changed, cost):
            a, b = ord(x) - 97, ord(y) - 97
            d[a][b] = min(d[a][b], c)
        for k in range(26):
            for i in range(26):
                for j in range(26):
                    if d[i][k] + d[k][j] < d[i][j]:
                        d[i][j] = d[i][k] + d[k][j]
        total = 0
        for x, y in zip(source, target):
            c = d[ord(x) - 97][ord(y) - 97]
            if c == INF:
                return -1
            total += c
        return total
    java
    long minimumCost(String source, String target, char[] original, char[] changed, int[] cost) {
        long INF = Long.MAX_VALUE / 4;
        long[][] d = new long[26][26];
        for (long[] row : d) Arrays.fill(row, INF);
        for (int i = 0; i < 26; i++) d[i][i] = 0;
        for (int i = 0; i < original.length; i++) {
            int a = original[i] - 'a', b = changed[i] - 'a';
            d[a][b] = Math.min(d[a][b], cost[i]);
        }
        for (int k = 0; k < 26; k++)
            for (int i = 0; i < 26; i++)
                for (int j = 0; j < 26; j++)
                    if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
        long total = 0;
        for (int i = 0; i < source.length(); i++) {
            long c = d[source.charAt(i) - 'a'][target.charAt(i) - 'a'];
            if (c >= INF) return -1;
            total += c;
        }
        return total;
    }
  10. 10

    Shortest palindrome by adding characters only at the front

    hard

    Find the longest prefix of s that is already a palindrome; the characters after it, reversed, go in front. Build t = s + "#" + reverse(s) and compute the KMP failure function. The last value is the length of the longest prefix of s that equals a suffix of reverse(s), which is the longest palindromic prefix. Time O(n), space O(n). Edge cases: already a palindrome (unchanged), empty string, all different characters (reverse of all but the first goes in front), the separator preventing overlap.

    python
    def shortest_palindrome(s):
        t = s + '#' + s[::-1]
        pi = [0] * len(t)
        for i in range(1, len(t)):
            k = pi[i - 1]
            while k and t[i] != t[k]:
                k = pi[k - 1]
            if t[i] == t[k]:
                k += 1
            pi[i] = k
        return s[pi[-1]:][::-1] + s
    java
    String shortestPalindrome(String s) {
        String t = s + "#" + new StringBuilder(s).reverse();
        int[] pi = new int[t.length()];
        for (int i = 1; i < t.length(); i++) {
            int k = pi[i - 1];
            while (k > 0 && t.charAt(i) != t.charAt(k)) k = pi[k - 1];
            if (t.charAt(i) == t.charAt(k)) k++;
            pi[i] = k;
        }
        return new StringBuilder(s.substring(pi[t.length() - 1])).reverse() + s;
    }

Frequently asked questions

What is edit distance used for?

It measures how different two strings are, and is used in spell checkers, fuzzy search and DNA alignment. In interviews it is the standard two-string DP.

How is regular expression matching different from wildcard matching?

In wildcard matching a star matches any sequence by itself. In the regex form a star repeats the preceding element zero or more times, so it cannot stand alone and the recurrence looks back two characters in the pattern.

How do I reduce the space for edit distance?

Keep only the previous row. Each cell depends on the cell above, to the left and diagonally up-left, so two rows (or one row and a saved diagonal) are enough.

How common are string DP questions in interviews?

Edit distance and wildcard matching are classic harder DP questions at product companies. The DSA coding round guide discusses how to allocate time across DP topics.

Related guides

More in DSA Interview Questions

See all in this section