Problem Statement

Given two strings str1 and str2, find the minimum number of insertions and deletions in string str1 required to transform str1 into str2.

Insertion and deletion of characters can take place at any position in the string.

Examples

Example 1:

Input: str1 = "kitten", str2 = "sitting"
Output: 5

Explanation: To transform "kitten" to "sitting", delete "k" and insert "s" to get "sitten", then insert "i" to get "sittin", and insert "g" at the end to get "sitting".

Example 2:

Input: str1 = "flaw", str2 = "lawn"
Output: 2

Explanation: To transform "flaw" to "lawn", delete "f" and insert "n" at the end. Hence minimum number of operations required is 2".

Different Approaches

1️⃣ Tabulation

Understanding:

We need to find the minimum operations required to convert string str1 to str2. Let us keep the “minimum” criteria aside and think, what maximum operations will be required for this conversion.

The easiest way is to remove all the characters of str1 and then insert all the characters of str2. In this way, we will convert str1 to str2 with ‘n+m’ operations. (Here n and m are the length of strings str1 and str2 respectively).

The problem states to find the minimum of insertions. Let us try to figure it out:

• To minimize the operations, we will first try to refrain from deleting those characters which are already present in str2. More extensively, we refrain from deleting those characters which are common and come in the same order. To minimize the operations, we would like to keep the maximum common characters coming in the same order intact. These maximum characters are the characters of the longest common subsequence.
• We will first keep the longest common subsequence of the str1 and str2 intact in str1 and delete all other characters from str1.

• Next, we will insert all the remaining characters of str2 to str1.

In order to minimize the operations, we need to find the length of the longest common subsequence(k):

Minimum Operations required = (n - k) + (m - k), Here 'n' and 'm' are the length of str1 and str2 respectively and 'k' is the length of the longest common subsequence of str1 and str2.

Approach:

1. Let 'n' and 'm' be the length of str1 and str2 respectively.
2. Find the length of the longest common subsequence ( say k) of str1 and str2 as discussed in Longest Common Subsequence.
3. Return (n-k) + (m-k) as answer.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution{
private:
    /* Function to calculate the length 
    of the Longest Common Subsequence*/
    int lcs(string s1, string s2) {
        int n = s1.size();
        int m = s2.size();
        
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1)); 

        // Initialize the base cases
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }
        for (int i = 0; i <= m; i++) {
            dp[0][i] = 0;
        }

        // Fill in the DP table to calculate the length of LCS
        for (int ind1 = 1; ind1 <= n; ind1++) {
            for (int ind2 = 1; ind2 <= m; ind2++) {
                
                // Characters match, increment LCS length
                if (s1[ind1 - 1] == s2[ind2 - 1])
                    dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1]; 
                /* Characters don't match, consider
                the maximum from left or above*/    
                else
                    dp[ind1][ind2] = max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1]); 
            }
        }
        // Return the length of Longest Common Subsequence
        return dp[n][m]; 
    }
public:
    /* Function to calculate the minimum insertions
    required to make a string palindrome*/
    int minOperations(string str1, string str2) {
        int n = str1.size();
        int m = str2.size();
    
        /* Calculate the length of the longest 
        common subsequence between str1 and str2*/
        int k = lcs(str1, str2);
    
        /* Calculate the minimum operations
        required to convert str1 to str2*/
        return (n - k) + (m - k);
    }
};
int main() {
    string str1 = "abcd";
    string str2 = "anc";
    
    //Create an instance of Solution class
    Solution sol;
    
    // Call the canYouMake function and print the result
    cout << "The Minimum operations required to convert str1 to str2: " <<sol.minOperations(str1, str2);
    return 0;
}

Complexity Analysis:

• Time Complexity: O(N*M), Where N is the length of string str1 and M is the length of str2. As we are using nested loops to solve the problem.
• Space Complexity: O(N*M), We are using an external array of size (N*M).

2️⃣ Space Optimization

If we observe the relations obtained in tabultaion approach, dp[ind1 - 1][ind2], dp[ind1][ind2 - 1]. We are using just two rows, dp[ind1-1][ ], dp[ind][ ], in order to calculate the present row.

So we are not required to contain an entire array, we can simply have two rows 'prev' and 'cur' where prev corresponds to dp[ind-1] and cur to dp[ind].

After declaring 'prev' and 'cur', replace dp[ind-1] to prev and dp[ind] with cur in the tabulation code. Following the same logic of tabulation, we will calculate cur[ind] in each iteration and after the inner loop executes, we will set prev = cur, so that the cur row can serve as prev for the next index.

After end of the execution, return prev[m] (m is the length of the string str2), as our answer, as it will hold the cumulative result of the overall calculation.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution{
private:
    /* Function to calculate the length 
    of the Longest Common Subsequence*/
    int lcs(string s1, string s2) {
        int n = s1.size();
        int m = s2.size();

        /* Declare two arrays to store the 
        previous and current rows of DP values*/
        vector<int> prev(m + 1, 0), cur(m + 1, 0);

        /* Base Case is covered as we have
        initialized the prev and cur to 0.*/

        for (int ind1 = 1; ind1 <= n; ind1++) {
            for (int ind2 = 1; ind2 <= m; ind2++) {
                if (s1[ind1 - 1] == s2[ind2 - 1])
                    cur[ind2] = 1 + prev[ind2 - 1];
                else
                    cur[ind2] = max(prev[ind2], cur[ind2 - 1]);
            }
            // Update the prev array with current values
            prev = cur;
        }
        // The value at prev[m] contains length of LCS
        return prev[m];
    }
public:
    /* Function to calculate the minimum insertions
    required to make a string palindrome*/
    int minOperations(string str1, string str2) {
        int n = str1.size();
        int m = str2.size();
    
        /* Calculate the length of the longest 
        common subsequence between str1 and str2*/
        int k = lcs(str1, str2);
    
        /* Calculate the minimum operations
        required to convert str1 to str2*/
        return (n - k) + (m - k);
    }
};
int main() {
    string str1 = "abcd";
    string str2 = "anc";
    
    //Create an instance of Solution class
    Solution sol;
    
    // Call the canYouMake function and print the result
    cout << "The Minimum operations required to convert str1 to str2: " <<sol.minOperations(str1, str2);
    return 0;
}

Complexity Analysis:

• Time Complexity: O(N*M), Where N is the length of string str1 and M is the length of str2. As we are using nested loops to solve the problem.
• Space Complexity: O(M), We are using an external array of size ‘M+1’ to store only two rows.