DP 30. Minimum Insertions/Deletions to Convert String A to String B

Converting one string to another using a minimum number of insertions and deletions is a classic algorithmic problem. This chapter explores how to minimize operations by identifying what parts of the strings can remain untouched, bridging the gap directly to the Longest Common Subsequence (LCS) pattern.

1. Problem Statement & Baseline Feasibility

Given two strings, str1 (of length $N$) and str2 (of length $M$), you are allowed two core operations on str1:

1. Delete any character in str1.
2. Insert any character anywhere in str1.

The objective is to transform str1 into str2 using the minimum possible number of operations (combined deletions and insertions).

Is a Solution Always Possible?

Yes, a valid sequence of operations always exists for any pair of strings.

• Worst-case scenario: You can delete all characters in str1 (requiring $N$ deletions) and then insert all characters of str2 one by one (requiring $M$ insertions).
• Total Operations (Naive Upper Bound): $N + M$ operations.

While $N + M$ always works, it is rarely the minimum. To minimize operations, we must touch as few characters as possible.

2. Core Mental Model: The "What Can We Not Touch?" Intuition

To minimize operations, the guiding philosophy is: Identify what you do not need to touch.

Real-Life Analogy

Mental Hook: Imagine editing an old manuscript (str1) into a newly revised publishing draft (str2). Instead of shredding the entire book and retyping every single word from scratch, you want to salvage as many matching paragraphs, sentences, or phrases as possible. The text you keep untouched requires zero effort; you only pay the cost of deleting unwanted words and inserting missing ones in the gaps.

If we want to minimize changes, we should keep the longest identical sequence of characters in both strings completely intact.

3. Step-by-Step Evolution: From Example to Formula

Let's trace a concrete example to see how deletions and insertions relate to the shared components of two strings:

• String 1 (str1): "abcd" (Length $N = 4$)
• String 2 (str2): "anc" (Length $M = 3$)

Analyzing the Transformation

1. Identify the Common Core: What is the longest matching portion between "abcd" and "anc"?
   • The common characters in order are 'a' and 'c'.
   • Thus, the longest matching subsequence is "ac", with a length of 2.
2. Determine Deletions: To reduce str1 ("abcd") down to just the matching core ("ac"), we must remove the characters that do not belong to the core.
   • Delete 'b' and 'd' ($2$ deletions).
   • Formula for Deletions: Length of str1 - Length of LCS $\rightarrow$ $4 - 2 = 2$.
3. Determine Insertions: Starting from the matching core ("ac"), we need to insert missing characters to build str2 ("anc").
   • Insert 'n' in the appropriate position ($1$ insertion).
   • Formula for Insertions: Length of str2 - Length of LCS $\rightarrow$ $3 - 2 = 1$.

4. Mathematical Derivation of Total Operations

By generalizing our manual walk-through, we can express the total operations mathematically using the Longest Common Subsequence (LCS):

5. Algorithmic Workflow & Implementation Strategy

Because this problem reduces directly to finding the Longest Common Subsequence, you do not need to invent a brand-new DP table from scratch.

Execution Flow

6. Code Implementation (C++ Reference)

Once you have your standard LCS utility function implemented, solving minimum insertions and deletions requires only a few lines of arithmetic wrapper code.

#int countMinOperations(string str1, string str2) {
    int n = str1.size();
    int m = str2.size();
    
    // Step 1: Find the length of the Longest Common Subsequence
    int lcsLength = lcs(str1, str2); 
    
    // Step 2: Calculate deletions and insertions
    int deletions = n - lcsLength;
    int insertions = m - lcsLength;
    
    // Step 3: Return total operations
    return deletions + insertions;
    // Alternatively: return n + m - 2 * lcsLength;
}

7. Complexity Analysis

Summary and Key Takeaways

• Problem Reduction: Converting str1 to str2 with minimum deletions and insertions is fundamentally an LCS problem in disguise.
• Invariance Principle: Focus on what you do not touch. Maximizing the untouched portion (the LCS) naturally minimizes the operations required.
• Deletion Count: Calculated as the total length of str1 minus the length of the LCS ($N - \text{LCS}$).
• Insertion Count: Calculated as the total length of str2 minus the length of the LCS ($M - \text{LCS}$).
• Combined Formula: Total operations equal $N + M - 2 \times \text{Length(LCS)}$.
• Code Reuse: Avoid writing duplicate logic; leverage existing space-optimized LCS routines to keep production code clean and maintainable.