Back to Strings
Q41Question 41 of 61

Minimum Deletions and Insertions to Transform One String into Another

Key Concepts
  • Deletions equal the first string's length minus the LCS length; insertions equal the second string's length minus the LCS length.
  • Characters in the LCS can stay untouched because they appear in both strings in the same relative order.
  • The LCS is computed with the standard prefix DP table: match adds 1 to the diagonal, mismatch keeps max(top, left).
  • Both deletion and insertion counts come from a single LCS computation.
  • This is simpler than full edit distance because it allows only deletions and insertions, not substitutions.
  • Time and space complexity are both O(m*n) for the LCS table.

Definition

Deletions equal first length minus common subsequence, insertions equal second length minus common subsequence.
  • Key insight is that characters in the LCS appear in both strings in the same relative order and can stay untouched.
  • Deletions equal len(A) - LCS, the characters in A that are not part of the shared subsequence.
  • Insertions equal len(B) - LCS, the characters in B that are not part of the shared subsequence.
  • Single LCS computation gives both answers.
  • Simpler than edit distance because substitutions are not allowed, only deletions and insertions.

The National Bank of India migrates old account labels into a new standard scheme. Whatever the two labels share in order is kept untouched. The rest of the old label is deleted, and the missing parts of the new label are inserted. The team wants the fewest total operations.

Understanding the Concepts

What is the problem?

Given two strings A and B, find the minimum number of deletions from A and insertions into it to transform A into B. Only deletions and insertions are allowed, not substitutions. For A="HEAP" and B="PEA", the LCS is "EA" (length 2), so deletions = 4-2 = 2 (remove H, P), insertions = 3-2 = 1 (add P at the end if needed), though the actual operations depend on the reconstruction.

JAVA
package com.bank.dsa;

public class MinDeleteInsert {
    public static int[] minOperations(String a, String b) {
        int m = a.length(), n = b.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        int lcs = dp[m][n];
        int deletions = m - lcs;
        int insertions = n - lcs;
        return new int[]{deletions, insertions};
    }
}

Why does this reduce to the LCS?

Any character belonging to the LCS appears in both strings in the same relative order and can stay in place during the transformation. Every character in A that is not part of the LCS must be deleted. Every character in B that is not part of the LCS must be inserted. So both operation counts derive from the single LCS length.

JAVA
package com.bank.dsa;

public class ReductionDemo {
    public static void main(String[] args) {
        String a = "ABCDEF", b = "AZBDCF";
        int[] ops = MinDeleteInsert.minOperations(a, b);
        int lcs = a.length() - ops[0];
        System.out.println("A: " + a + " (length " + a.length() + ")");
        System.out.println("B: " + b + " (length " + b.length() + ")");
        System.out.println("LCS length: " + lcs);
        System.out.println("Deletions from A: " + ops[0]);
        System.out.println("Insertions for B: " + ops[1]);
    }
}
TEXT
A: ABCDEF (length 6)
B: AZBDCF (length 6)
LCS length: 4
Deletions from A: 2
Insertions for B: 2

How does the LCS DP work?

The table dp[i][j] holds the LCS length of the first i characters of A and the first j characters of B. On a match, add 1 to the diagonal. On a mismatch, keep the max of the cell above or to the left. The LCS length is in dp[m][n].

JAVA
package com.bank.dsa;

public class LCSDemo {
    public static void main(String[] args) {
        String a = "OLD", b = "NEW";
        int[][] dp = new int[a.length() + 1][b.length() + 1];
        for (int i = 1; i <= a.length(); i++) {
            for (int j = 1; j <= b.length(); j++) {
                dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1)
                    ? 1 + dp[i - 1][j - 1]
                    : Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        int lcs = dp[a.length()][b.length()];
        System.out.println("LCS(" + a + ", " + b + ") = " + lcs);
        System.out.println("Deletions: " + (a.length() - lcs));
        System.out.println("Insertions: " + (b.length() - lcs));
    }
}
TEXT
LCS(OLD, NEW) = 0
Deletions: 3
Insertions: 3

How is this different from edit distance?

Edit distance (Levenshtein distance) allows three operations: insert, delete, and substitute. This problem allows only two: insert and delete. Without substitution, transforming one character into another requires one deletion plus one insertion (cost 2), whereas edit distance counts that as one substitution (cost 1). The insert-delete problem maps directly to the LCS.

| Problem | Operations | Uses |
|---|---|---|
| This problem | Delete + Insert | LCS |
| Edit distance | Delete + Insert + Substitute | DP with 3 choices |
| Total ops here | (m - LCS) + (n - LCS) | m + n - 2*LCS |

JAVA
package com.bank.dsa;

public class VsEditDistanceDemo {
    public static void main(String[] args) {
        String a = "ABC", b = "AXC";
        int[] ops = MinDeleteInsert.minOperations(a, b);
        System.out.println("Delete+Insert: " + ops[0] + " deletions + " + ops[1] + " insertions = " + (ops[0] + ops[1]) + " total");
        // Edit distance with substitution would be 1 (replace B with X)
        System.out.println("Edit distance would be: 1 (substitute B→X)");
    }
}
DIAGRAM
Delete+Insert: 1 deletions + 1 insertions = 2 total
Edit distance would be: 1 (substitute B→X)

What are the edge cases?

If both strings are identical, LCS equals their length, so 0 deletions and 0 insertions. If they share no common character, all of A is deleted and all of B is inserted. If one string is empty, all operations are insertions or deletions.

JAVA
package com.bank.dsa;

public class EdgeCaseDemo {
    public static void main(String[] args) {
        int[] same = MinDeleteInsert.minOperations("ABC", "ABC");
        System.out.println("Same: del=" + same[0] + " ins=" + same[1]);

        int[] diff = MinDeleteInsert.minOperations("ABC", "XYZ");
        System.out.println("All diff: del=" + diff[0] + " ins=" + diff[1]);

        int[] empty = MinDeleteInsert.minOperations("", "ABC");
        System.out.println("Empty→ABC: del=" + empty[0] + " ins=" + empty[1]);
    }
}
DIAGRAM
Same: del=0 ins=0
All diff: del=3 ins=3
Empty→ABC: del=0 ins=3

What is the time and space complexity?

Time is O(m*n) for the LCS computation. Space is O(m*n) for the table, reducible to O(min(m,n)) with rolling rows. Both answers come from a single computation.

What are common mistakes?

Forgetting that the total operations are deletions plus insertions, not just one of them. Confusing this with edit distance which allows substitutions. Using the common substring instead of the common subsequence, which would give a wrong LCS value.

What are common interview follow-up questions?

  • How would you reconstruct the actual sequence of operations?
  • How does this relate to the shortest common supersequence problem?
  • What if deletions and insertions have different costs?
  • How would you solve this with edit distance allowing substitutions?

Visual Overview

DIAGRAM
  A = "ABCDEF" (m=6)
  B = "AZBDCF" (n=6)

  LCS = "ABCF" (length 4)

  Characters in A not in LCS: E, remaining from mismatches
  Characters in B not in LCS: Z, remaining from mismatches

  ┌──────────────────────────────────────┐
  │  A:  A  B  C  D  E  F               │
  │  LCS: A  B  C        F  (keep these) │
  │  Delete: D, E  (m - LCS = 6 - 4 = 2)│
  └──────────────────────────────────────┘

  ┌──────────────────────────────────────┐
  │  B:  A  Z  B  D  C  F               │
  │  LCS: A     B     C  F  (keep these) │
  │  Insert: Z, D  (n - LCS = 6 - 4 = 2)│
  └──────────────────────────────────────┘

  Total operations: 2 + 2 = 4

Key Takeaway

The Minimum Deletions and Insertions to Transform One String into Another is a clean application of the LCS pattern. The key insight is that characters in the longest common subsequence already appear in both strings in the same order and can stay untouched. Everything else in the first string must be deleted, and everything missing from the second string must be inserted.

Rajesh at the National Bank of India uses this during label migration: the old account label needs to become the new standard label with the fewest changes. He computes the LCS once, and both the deletion count (m - LCS) and the insertion count (n - LCS) fall out of that single computation. No separate DP is needed.

The distinction from full edit distance is important: this problem allows only deletions and insertions, not substitutions. Without substitution, changing one character to another costs 2 operations (one delete, one insert), whereas edit distance counts it as 1 substitution. This makes the insert-delete problem map directly to the LCS rather than requiring the full edit distance DP.

The time and space are both O(m*n) for the LCS table. If both strings are identical, zero operations are needed. If they share nothing, all of the first is deleted and all of the second is inserted.

Remember one sentence: compute the LCS once, then deletions equal first length minus LCS and insertions equal second length minus LCS.

---

Share
Use ← → arrow keys to navigate