Skip to main content
String DP

Edit Distance

Minimum operations (insert, delete, replace) to transform one string into another. At each pair of characters: if they match, no cost. Otherwise, try all three operations and take the minimum.

O(m*n)
·
O(m*n)

How It Works

Edit distance (Levenshtein distance) counts the minimum insertions, deletions, and replacements to turn one string into another. Let dp[i][j] be the distance between the first i characters of word A and first j of word B. If the current characters match, dp[i][j] = dp[i−1][j−1] with no cost. Otherwise it is 1 plus the minimum of three predecessors: dp[i−1][j] (delete), dp[i][j−1] (insert), and dp[i−1][j−1] (replace).

Base cases are the empty-string rows: transforming from or to an empty string costs the other string's length. The table fills in O(m·n) time, avoiding the exponential search over all operation sequences, and rolls down to O(min(m, n)) space when only the distance is needed.

Step-by-Step Visualization

Edit distance: 'horse' → 'ros'
h
0
o
1
r
2
s
3
e
4
word1horse
word2ros
1/3

Code

Java
static int minDistance(String word1, String word2) {
  int m = word1.length(), n = word2.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] = word1.charAt(i-1) == word2.charAt(j-1)
        ? dp[i-1][j-1]
        : 1 + Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1]));

  return dp[m][n];
}

Tips & Gotchas

1If chars match: dp[i][j] = dp[i-1][j-1] (no operation needed)
2If different: min of insert, delete, replace (each +1)
3dp[i][j] = min edits to convert s1[0..i] to s2[0..j]

Practice Problems

  • 1Edit Distance
  • 2One Edit Distance
  • 3Delete Operation for Two Strings
  • 4Minimum ASCII Delete Sum for Two Strings

About the String DP Pattern

When string problems involve comparing two strings character by character (subsequences, transformations, matching), dynamic programming builds the solution from smaller substrings up to the full strings.

Key insight

Think of strings as arrays of characters. Frequency maps solve most comparison problems. For substring search, know KMP or rolling hash to beat O(n·m).

Common String Interview Problems

  • Longest Substring Without Repeating Characters
  • Valid Anagram
  • Longest Palindromic Substring
  • Minimum Window Substring
  • Group Anagrams

Frequently Asked Questions

How do the three dp transitions map to actual edit operations?

Moving from dp[i−1][j] deletes a character from the source, dp[i][j−1] inserts the target's current character, and dp[i−1][j−1] replaces one character with another. Visualizing the table this way also lets you reconstruct the exact operation sequence by backtracking.

Can edit distance be computed faster than O(m·n)?

Not substantially in the general case — strongly subquadratic algorithms would violate the Strong Exponential Time Hypothesis. If you only need to know whether the distance is at most k, a banded DP restricted to a diagonal strip runs in O(k · min(m, n)).