Minimum Number Of Deletions And Insertions

Given two strings str1 and str2. The task is to remove or insert the minimum number of characters from/in str1 so as to transform it into str2. It could be possible that the same character needs to be removed/deleted from one point of str1 and inserted to some another point.

Examples :

Input: str1 = "heap", str2 = "pea"
Output: 3
Explanation: 2 deletions and 1 insertion.
p and h deleted from heap. Then, p is inserted at the beginning.
One thing to note, though p was required yet it was removed/deleted first from its position and then it is inserted to some other position. Thus, p contributes one to the deletion_count and one to the insertion_count.

Input : str1 = "geeksforgeeks", str2 = "geeks"
Output: 8
Explanation: 8 deletions, i.e. remove all characters of the string "forgeeks".

Expected Time Complexity: O(|str1|*|str2|)
Expected Space Complexity: O(|str1|*|str2|)

Constraints:
1 ≤ |str1|, |str2| ≤ 1000
All the characters are lowercase English alphabets

Approach 01:

class Solution {
    int longestCommonSubsequence(string& str1, string& str2, int index1, int index2, vector<vector<int>>& memo) {
        if (index1 < 0 || index2 < 0) 
            return 0;
        if (memo[index1][index2] != -1) 
            return memo[index1][index2];
        if (str1[index1] == str2[index2]) 
            return memo[index1][index2] = 1 + longestCommonSubsequence(str1, str2, index1 - 1, index2 - 1, memo);
        else {
            return memo[index1][index2] = max(
                longestCommonSubsequence(str1, str2, index1 - 1, index2, memo),
                longestCommonSubsequence(str1, str2, index1, index2 - 1, memo)
            );
        }
    }

    int computeLCS(string& str1, string& str2) {
        vector<vector<int>> memo(str1.length(), vector<int>(str2.length(), -1));
        return longestCommonSubsequence(str1, str2, str1.length() - 1, str2.length() - 1, memo);
    }

public:
    int minOperations(string str1, string str2) { 
        return str1.length() + str2.length() - 2 * computeLCS(str1, str2);
    } 
};

class Solution:
    def longestCommonSubsequence(self, str1, str2, index1, index2, memo):
        if index1 < 0 or index2 < 0:
            return 0
        if memo[index1][index2] != -1:
            return memo[index1][index2]
        if str1[index1] == str2[index2]:
            memo[index1][index2] = 1 + self.longestCommonSubsequence(str1, str2, index1 - 1, index2 - 1, memo)
        else:
            memo[index1][index2] = max(
                self.longestCommonSubsequence(str1, str2, index1 - 1, index2, memo),
                self.longestCommonSubsequence(str1, str2, index1, index2 - 1, memo)
            )
        return memo[index1][index2]

    def computeLCS(self, str1, str2):
        memo = [[-1] * len(str2) for _ in range(len(str1))]
        return self.longestCommonSubsequence(str1, str2, len(str1) - 1, len(str2) - 1, memo)

    def minOperations(self, str1, str2):
        return len(str1) + len(str2) - 2 * self.computeLCS(str1, str2)

Time Complexity

• Longest Common Subsequence (LCS) Calculation

  The function longestCommonSubsequence uses memoization to store previously computed results in a 2D vector, memo. Since the function explores all possible combinations of indices in the two strings, the maximum number of recursive calls is proportional to the product of the lengths of the two strings, i.e., \( O(m \times n) \), where m and n are the lengths of str1 and str2, respectively.

• Overall Time Complexity

  The overall time complexity of the function is \( O(m \times n) \) due to the memoization approach, which ensures each subproblem is solved only once.

Space Complexity

• Auxiliary Space for Memoization

  The memoization table, memo, requires \( O(m \times n) \) space to store results for each subproblem, where m and n are the lengths of str1 and str2, respectively.

• Recursive Call Stack Space

  In the worst case, the recursive depth could go up to \( O(m + n) \), representing the space required by the call stack for the recursive function calls.

• Overall Space Complexity

  The overall space complexity is \( O(m \times n) \) due to the memoization table, as it dominates the space used by the call stack.