Minimum number of insertions and deletions to convert string from one to another

Problem Statement

Given two strings str1 and str2, you need to transform str1 into str2 using the minimum number of operations.
Allowed operations:

Insertion
Deletion

Note: Character replacement is not allowed.

Intuition

To minimize the number of operations, we should try to preserve the common parts of both strings.
That common part is the Longest Common Subsequence (LCS) of the two strings.

If:

n = str1.length()
m = str2.length()
lcs = length of Longest Common Subsequence(str1, str2)

Then:

Deletions needed = n - lcs
Insertions needed = m - lcs
Total operations = deletions + insertions

Example

str1 = "heap"
str2 = "pea"

LCS = "ea"

Deletions = 4 - 2 = 2  
Insertions = 3 - 2 = 1

Total Operations = 2 + 1 = 3

Dry Run

str1 = "geek"
str2 = "gesek"

LCS = "gek" (length = 3)

Deletions = 4 - 3 = 1  
Insertions = 5 - 3 = 2  

Total Operations = 3

Approach Overview

The core task is to compute the LCS of str1 and str2, and then use the formulas:

Deletions = str1.length() - LCS
Insertions = str2.length() - LCS
Total Operations = Deletions + Insertions

1. Recursive LCS Approach

Java Code

class Solution {
    public int minOperations(String str1, String str2) {
        int lcsLength = lcs(str1, str2, str1.length(), str2.length());
        return (str1.length() - lcsLength) + (str2.length() - lcsLength);
    }

    private int lcs(String a, String b, int i, int j) {
        if (i == 0 || j == 0) return 0;

        if (a.charAt(i - 1) == b.charAt(j - 1)) {
            return 1 + lcs(a, b, i - 1, j - 1);
        } else {
            return Math.max(
                lcs(a, b, i - 1, j),
                lcs(a, b, i, j - 1)
            );
        }
    }
}

Time and Space Complexity

Metric	Value
Time	Exponential O(2^n)
Space	O(n + m) (call stack)

2. Memoized LCS (Top-down DP)

Java Code

class Solution {
    public int minOperations(String str1, String str2) {
        int n = str1.length(), m = str2.length();
        Integer[][] dp = new Integer[n + 1][m + 1];
        int lcsLength = lcs(str1, str2, n, m, dp);
        return (n - lcsLength) + (m - lcsLength);
    }

    private int lcs(String a, String b, int i, int j, Integer[][] dp) {
        if (i == 0 || j == 0) return 0;

        if (dp[i][j] != null) return dp[i][j];

        if (a.charAt(i - 1) == b.charAt(j - 1)) {
            dp[i][j] = 1 + lcs(a, b, i - 1, j - 1, dp);
        } else {
            dp[i][j] = Math.max(
                lcs(a, b, i - 1, j, dp),
                lcs(a, b, i, j - 1, dp)
            );
        }

        return dp[i][j];
    }
}

Time and Space Complexity

Metric	Value
Time	O(n × m)
Space	O(n × m) (dp) + O(n + m) (stack)

3. Tabulation (Bottom-up DP)

Java Code

class Solution {
    public int minOperations(String str1, String str2) {
        int n = str1.length(), m = str2.length();
        int[][] dp = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (str1.charAt(i - 1) == str2.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[n][m];
        return (n - lcs) + (m - lcs);
    }
}

Time and Space Complexity

Metric	Value
Time	O(n × m)
Space	O(n × m)

Optional: Space Optimized Tabulation

You can reduce space to O(m) using two 1D arrays (prev and curr) since each row depends only on the previous row.

Let me know if you want this version as well.

Summary

Approach	Time Complexity	Space Complexity	Suitable For
Recursion	O(2^n)	O(n + m)	Very small input only
Memoization	O(n × m)	O(n × m)	Medium to large input
Tabulation	O(n × m)	O(n × m)	Efficient, preferred

Final Formula

Total Operations = (str1.length() - LCS) + (str2.length() - LCS)
                 = str1.length() + str2.length() - 2 × LCS