Minimum insertions or deletions to convert string A to B

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:

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

#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;
}


import java.util.*;

class Solution {
    /* Function to calculate the length 
    of the Longest Common Subsequence*/
    private int lcs(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        
        int[][] dp = new int[n + 1][m + 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.charAt(ind1 - 1) == s2.charAt(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] = Math.max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1]);
            }
        }
        // Return the length of Longest Common Subsequence
        return dp[n][m];
    }
    /* Function to calculate the minimum insertions
    required to make a string palindrome*/
    public int minOperations(String str1, String str2) {
        int n = str1.length();
        int m = str2.length();
    
        /* 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);
    }

    public static void main(String[] args) {
        String str1 = "abcd";
        String str2 = "anc";
        
        // Create an instance of Solution class
        Solution sol = new Solution();
        
        // Call the minOperations function and print the result
        System.out.println("The Minimum operations required to convert str1 to str2: " + sol.minOperations(str1, str2));
    }
}
class Solution:
    """ Function to calculate the length 
    of the Longest Common Subsequence"""
    def lcs(self, s1, s2):
        n = len(s1)
        m = len(s2)
        
        # Initialize the DP table
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        
        # Fill in the DP table to calculate length of LCS
        for ind1 in range(1, n + 1):
            for ind2 in range(1, m + 1):
                
                # Characters match, increment LCS length
                if s1[ind1 - 1] == s2[ind2 - 1]:
                    dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1]
            
                else:
                    dp[ind1][ind2] = max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1])
        
        # Return the length of Longest Common Subsequence
        return dp[n][m]

    """ Function to calculate the minimum insertions
    required to make a string palindrome"""
    def minOperations(self, str1, str2):
        n = len(str1)
        m = len(str2)
    
        """ Calculate the length of the longest 
        common subsequence between str1 and str2"""
        k = self.lcs(str1, str2)
    
        """ Calculate the minimum operations
        required to convert str1 to str2"""
        return (n - k) + (m - k)

if __name__ == "__main__":
    str1 = "abcd"
    str2 = "anc"
    
    # Create an instance of Solution class
    sol = Solution()
    
    # Call the minOperations function and print the result
    print("The Minimum operations required to convert str1 to str2:", sol.minOperations(str1, str2))
class Solution {
    /* Function to calculate the length 
    of the Longest Common Subsequence*/
    lcs(s1, s2) {
        const n = s1.length;
        const m = s2.length;
        
        // Initialize the DP table
        const dp = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0));
        
        // Fill in the DP table to calculate length of LCS
        for (let ind1 = 1; ind1 <= n; ind1++) {
            for (let 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] = Math.max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1]);
            }
        }
        // Return the length of Longest Common Subsequence
        return dp[n][m];
    }
    /* Function to calculate the minimum insertions
    required to make a string palindrome*/
    minOperations(str1, str2) {
        const n = str1.length;
        const m = str2.length;
    
        /* Calculate the length of the longest 
        common subsequence between str1 and str2*/
        const k = this.lcs(str1, str2);
    
        /* Calculate the minimum operations
        required to convert str1 to str2*/
        return (n - k) + (m - k);
    }
}

// Create an instance of Solution class
const sol = new Solution();

// Call minOperations function and print the result
const str1 = "abcd";
const str2 = "anc";
console.log("The Minimum operations required to convert str1 to str2: " + sol.minOperations(str1, str2));

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).

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.

#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;
}
class Solution {
    /* Function to calculate the length 
    of the Longest Common Subsequence */
    private int lcs(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();

        /* Declare two arrays to store the previous 
        and current rows of DP values */
        int[] prev = new int[m + 1];
        int[] cur = new int[m + 1];

        /* 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.charAt(ind1 - 1) == s2.charAt(ind2 - 1)) {
                    cur[ind2] = 1 + prev[ind2 - 1];
                } else {
                    cur[ind2] = Math.max(prev[ind2], cur[ind2 - 1]);
                }
            }
            // Update the prev array with current values
            prev = cur.clone(); // Copying the current array to the previous array
        }
        // The value at prev[m] contains the length of LCS
        return prev[m];
    }

    /* Function to calculate the minimum insertions 
    required to make a string palindrome */
    public int minOperations(String str1, String str2) {
        int n = str1.length();
        int m = str2.length();

        /* 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);
    }
}

class Main {
    public static void main(String[] args) {
        String str1 = "abcd";
        String str2 = "anc";
        
        // Create an instance of Solution class
        Solution sol = new Solution();
        
        // Call the minOperations function and print the result
        System.out.println("The Minimum operations required to convert str1 to str2: " + sol.minOperations(str1, str2));
    }
}
class Solution:
    """ Function to calculate the length 
    of the Longest Common Subsequence"""
    def lcs(self, s1, s2):
        n = len(s1)
        m = len(s2)

        """ Declare two arrays to store the previous
        and current rows of DP values"""
        prev = [0] * (m + 1)
        cur = [0] * (m + 1)

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

        for ind1 in range(1, n + 1):
            for ind2 in range(1, m + 1):
                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.copy()
        
        # The value at prev[m] contains length of LCS
        return prev[m]

    """ Function to calculate the minimum insertions
    required to make a string palindrome"""
    def minOperations(self, str1, str2):
        n = len(str1)
        m = len(str2)

        """ Calculate the length of the longest 
        common subsequence between str1 and str2"""
        k = self.lcs(str1, str2)

        """ Calculate the minimum operations
        required to convert str1 to str2"""
        return (n - k) + (m - k)

if __name__ == "__main__":
    str1 = "abcd"
    str2 = "anc"

    # Create an instance of Solution class
    sol = Solution()

    # Call the minOperations function and print the result
    print("The Minimum operations required to convert str1 to str2:", sol.minOperations(str1, str2))
class Solution {
    /* Function to calculate the length 
    of the Longest Common Subsequence*/
    lcs(s1, s2) {
        const n = s1.length;
        const m = s2.length;

        /* Create two arrays to store the 
        previous and current rows of DP values*/
        const prev = new Array(m + 1).fill(0);
        const cur = new Array(m + 1).fill(0);

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

        for (let ind1 = 1; ind1 <= n; ind1++) {
            for (let ind2 = 1; ind2 <= m; ind2++) {
                if (s1[ind1 - 1] === s2[ind2 - 1])
                    cur[ind2] = 1 + prev[ind2 - 1];
                else
                    cur[ind2] = Math.max(prev[ind2], cur[ind2 - 1]);
            }
            // Update the prev array with current values
            prev.splice(0, prev.length, ...cur);
        }
        // The value at prev[m] contains length of LCS
        return prev[m];
    }
    /* Function to calculate the minimum insertions
    required to make a string palindrome*/
    minOperations(str1, str2) {
        const n = str1.length;
        const m = str2.length;

        /* Calculate the length of the longest 
        common subsequence between str1 and str2*/
        const k = this.lcs(str1, str2);

        /* Calculate the minimum operations
        required to convert str1 to str2*/
        return (n - k) + (m - k);
    }
}
const str1 = "abcd";
const str2 = "anc";

// Create an instance of Solution class
const sol = new Solution();

// Call minOperations function and print the result
console.log("The Minimum operations required to convert str1 to str2: " + sol.minOperations(str1, str2));

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.

Problem List

Minimum insertions or deletions to convert string A to B

Examples:

Constraints

Hints

Company Tags

Editorial

Understanding:

Approach:

Complexity Analysis:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code