☕ DSA Java Articles

Topics › Dynamic Programming › DP on Strings

Minimum insertions or deletions to convert string A to B

Hard TUF ID 311 A2Z

Java source ↗ Edit this article ↗

Problem

You are given two strings a and b. In one operation you may either delete one character from a or insert one character anywhere into a. Return the minimum number of operations that turn a into b. (There is no “replace” operation; that would make it Edit distance.)

Constraints: 1 ≤ n, m ≤ 1000 in the usual version; the Java methods also accept empty strings.

Example 1

a = "heap", b = "pea"
answer = 3          // delete 'h' and the last 'p' -> "ea", insert 'p' at the front -> "pea"

Example 2

a = "abcd", b = "anc"
answer = 3          // keep "ac": delete 'b' and 'd', insert 'n'

Key insight: count what you keep

Some characters of a are never touched. They stay in their original order and end up as characters of b, so they form a common subsequence of a and b. Every other character of a must be deleted, and every other character of b must be inserted. If k characters are kept, the cost is (n - k) + (m - k).

To minimise the cost, maximise k: keep a Longest common subsequence. Therefore

answer = (n - LCS) deletions + (m - LCS) insertions = n + m - 2 · LCS

For Example 1, LCS("heap", "pea") = 2 ("ea"), so 4 + 3 - 4 = 3. Inserting before deleting, or in any other order, never helps: inserted characters are never deleted in an optimal plan, since that would waste two operations.

The same count also has its own direct recurrence on prefixes. Let f(i, j) be the fewest operations turning a[0..i) into b[0..j):

Approaches 1 to 4 build this recurrence up in the usual DP steps; Approach 5 uses the LCS formula.

Approach 1: Recursion

Intuition. Compare the last characters. If they agree, keeping them is safe, for the same exchange reason that LCS always matches equal last characters. If they differ, one of them is not kept: either a’s last character is deleted or b’s last character is inserted.

Algorithm.

  1. If i == 0 return j; if j == 0 return i.
  2. On a match return f(i - 1, j - 1).
  3. Otherwise return 1 + min(f(i - 1, j), f(i, j - 1)).
static int recursive(String a, String b) {
    return solve(a.length(), b.length(), a, b);
}

/** Fewest operations that turn the prefix a[0..i) into the prefix b[0..j). */
static int solve(int i, int j, String a, String b) {
    if (i == 0) return j;                                    // insert all of b[0..j)
    if (j == 0) return i;                                    // delete all of a[0..i)
    if (a.charAt(i - 1) == b.charAt(j - 1)) return solve(i - 1, j - 1, a, b);   // keep the matching last character
    return 1 + Math.min(solve(i - 1, j, a, b),               // delete a[i - 1]
                        solve(i, j - 1, a, b));              // insert b[j - 1] at the end
}

Complexity. Time O(2^(n + m)): with no matches each call branches twice and the depth is n + m. Space O(n + m) for the stack.

Approach 2: Memoization

Intuition. Deleting then inserting, or inserting then deleting, lead to the same (i, j). There are only (n + 1)(m + 1) states, so cache them; -1 marks “not computed”. The base cases return before the cache is read, so they need no entries.

Algorithm.

  1. dp[n + 1][m + 1] filled with -1.
  2. Same recursion, returning stored values and storing new ones.
static int memoization(String a, String b) {
    int n = a.length(), m = b.length();
    int[][] dp = new int[n + 1][m + 1];
    for (int[] row : dp) Arrays.fill(row, -1);
    return memo(n, m, a, b, dp);
}

static int memo(int i, int j, String a, String b, int[][] dp) {
    if (i == 0) return j;
    if (j == 0) return i;
    if (dp[i][j] != -1) return dp[i][j];
    if (a.charAt(i - 1) == b.charAt(j - 1)) return dp[i][j] = memo(i - 1, j - 1, a, b, dp);
    return dp[i][j] = 1 + Math.min(memo(i - 1, j, a, b, dp), memo(i, j - 1, a, b, dp));
}

Complexity. Time O(n · m), space O(n · m) plus O(n + m) stack.

Approach 3: Tabulation

Intuition. Unlike LCS, the base cases are not zero: dp[i][0] = i and dp[0][j] = j. Fill those first, then the rest row by row, left to right, since each cell reads the cells above, to the left, and diagonally up-left.

Algorithm.

  1. dp[i][0] = i, dp[0][j] = j.
  2. For i = 1 .. n, j = 1 .. m: apply the recurrence.
  3. Return dp[n][m].
static int tabulation(String a, String b) {
    int n = a.length(), m = b.length();
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 0; i <= n; i++) dp[i][0] = i;
    for (int j = 0; j <= m; j++) dp[0][j] = j;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
            else dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[n][m];
}

Dry run on Example 1, a = "heap" (rows), b = "pea" (columns):

  ”” p e a
”” 0 1 2 3
h 1 2 3 4
e 2 3 2 3
a 3 4 3 2
p 4 3 4 3

The bold cells are the matches e and a, which copy their upper-left neighbour at no cost. At the corner p ≠ a, so it takes 1 + min(dp[3][3], dp[4][2]) = 1 + 2 = 3: turn "hea" into "pea" in two steps, then delete the trailing p.

Complexity. Time O(n · m), space O(n · m).

Approach 4: Space optimized

Intuition. Each row reads only the previous row and itself. Keep two rows. The detail that is easy to miss: each new row starts with its own base case, cur[0] = i (delete all i characters), which must be written before filling the rest of the row.

Algorithm.

  1. prev[j] = j for row 0.
  2. For each i: cur[0] = i, fill cur[1..m], swap.
  3. Return prev[m].
static int spaceOptimized(String a, String b) {
    int n = a.length(), m = b.length();
    int[] prev = new int[m + 1], cur = new int[m + 1];
    for (int j = 0; j <= m; j++) prev[j] = j;
    for (int i = 1; i <= n; i++) {
        cur[0] = i;
        for (int j = 1; j <= m; j++) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) cur[j] = prev[j - 1];
            else cur[j] = 1 + Math.min(prev[j], cur[j - 1]);
        }
        int[] tmp = prev; prev = cur; cur = tmp;
    }
    return prev[m];
}

Complexity. Time O(n · m), space O(m).

Approach 5: Via LCS

Intuition. Compute the LCS length with two rows and apply n + m - 2 · LCS. It is the same amount of work as Approach 4, but it also tells you the split: n - LCS deletions and m - LCS insertions, which some versions of the problem ask for separately.

static int viaLcs(String a, String b) {
    int n = a.length(), m = b.length();
    int[] prev = new int[m + 1], cur = new int[m + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) cur[j] = 1 + prev[j - 1];
            else cur[j] = Math.max(prev[j], cur[j - 1]);
        }
        int[] tmp = prev; prev = cur; cur = tmp;
    }
    int lcs = prev[m];
    return (n - lcs) + (m - lcs);                            // deletions + insertions
}

Complexity. Time O(n · m), space O(m).

Edge cases and pitfalls