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 distance | O(m * n) time, O(n) space |
|---|---|
| Matching problems | dp[i][j] over prefixes of text and pattern |
| Palindromes | Expand around centres, O(n^2) |
| Operations | Insert, 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
- Forgetting the first row and column, which hold the cost of building from or deleting to the empty string.
- Treating a star in regular expressions as a standalone wildcard instead of a modifier of the previous character.
- Mixing one-based table indexes with zero-based string indexes.
- Using the same dp[i][j] meaning for wildcard and regex, where the star rules differ.
- Assuming edit distance operations all cost 1 when the problem gives weights.
Edit Distance and String DP Interview Questions: questions with worked answers
1 One edit distance: are two strings exactly one edit apart?
easyCompare 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.
pythondef 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) == 1javaboolean 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 Edit distance (Levenshtein)
mediumdp[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).
pythondef 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]javaint 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 List the actual edit operations
mediumKeep 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.
pythondef 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]javaList<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 Count palindromic substrings
mediumEvery 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.
pythondef 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 countjavaint 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 Palindrome partitioning II: minimum cuts
hardPrecompute 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.
pythondef 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]javaint 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 Longest valid parentheses
hardLet 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.
pythondef 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 bestjavaint 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 Wildcard matching with ? and *
harddp[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.
pythondef 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]javaboolean 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 Regular expression matching with . and *
hardHere 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.
pythondef 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]javaboolean 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 Minimum cost to convert one string into another with letter conversion rules
mediumEach 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.
pythondef 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 totaljavalong 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 Shortest palindrome by adding characters only at the front
hardFind 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.
pythondef 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] + sjavaString 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
- Fast and slow pointers interview questions with solutions
- Fenwick Tree (Binary Indexed Tree) Interview Questions
- Graph Interview Questions and Answers
- Greedy algorithm interview questions with worked solutions
- Grid and Matrix DP Interview Questions
- Hashing interview questions with worked solutions
- Heap and Priority Queue Interview Questions
- Interval DP Interview Questions
- Interval interview questions with worked solutions
- Kadane algorithm interview questions with worked solutions
- KMP and string matching interview questions with solutions
- Knapsack DP Interview Questions