Minimum ASCII Delete Sum for Two Strings

class Solution {
public:
    int minDeleteCost(string str1, string str2) {
        
        if (str1.length() < str2.length()) {
            return minDeleteCost(str2, str1);
        }
        
        int len1 = str1.length(), len2 = str2.length();
        vector<int> dp(len2 + 1);
        for (int j = 1; j <= len2; j++) {
            dp[j] = dp[j - 1] + str2[j - 1];
        }
        
        for (int i = 1; i <= len1; i++) {
            
            int previous = dp[0];
            dp[0] += str1[i - 1];
            
            for (int j = 1; j <= len2; j++) {

                int tempAns;
                
                if (str1[i - 1] == str2[j - 1]) {
                    tempAns = previous;
                }
                else {
                    tempAns = min(
                        str1[i - 1] + dp[j],
                        str2[j - 1] + dp[j - 1]
                    );
                }
                
                previous = dp[j];
                dp[j] = tempAns;
            }
        }
        
        return dp[len2];
    }
};

This C++ code provides a solution for calculating the minimum ASCII deletion sum for two given strings by implementing a dynamic programming approach.

• Start by checking the lengths of the two strings. If the first string is shorter than the second, they are swapped to ensure that the first string is the longer one. This reduces the problem size potentially and ensures that the space complexity is optimized.
• Initialize variables for the lengths of the strings (len1 and len2).
• Use a dynamic programming array dp initialized to a size of len2 + 1. The elements of dp are filled with cumulative ASCII values of characters from str2 up to the current index.
• Iterate over each character of str1 with i representing the index in str1.
• Within this loop, for each character in str2 indexed by j, calculate the minimum ASCII deletion sum if the characters at the current positions in str1 and str2 match or do not.
• previous maintains the value of dp[j] before it is updated, representing the cost up to previous characters.
• If the current characters in str1 and str2 match (str1[i-1] == str2[j-1]), then tempAns is assigned the value of previous. If they do not match, calculate the minimum cost by considering either deleting the current character from str1 or from str2 and add the respective deletion costs.
• Assign the calculated minimum cost to dp[j].
• After all iterations, dp[len2] contains the minimum ASCII deletion sum for fully transforming both strings by removing characters.

This implementation efficiently computes the result in O(len1 * len2) time complexity and uses O(len2) space complexity, providing a scalable solution to problems involving finding the minimum cost of string transformations by ASCII value deletions.

class Solution {
    public int minDeletionCost(String str1, String str2) {
        
        // Swap to ensure first string is larger
        if (str1.length() < str2.length()) {
            return minDeletionCost(str2, str1);
        }
        
        int len1 = str1.length(), len2 = str2.length();
        int[] dp = new int[len2 + 1];
        for (int j = 1; j <= len2; j++) {
            dp[j] = dp[j - 1] + str2.charAt(j - 1);
        }
        
        // Dynamic programming to compute results
        for (int i = 1; i <= len1; i++) {
            
            int previous = dp[0];
            dp[0] += str1.charAt(i - 1);
            
            for (int j = 1; j <= len2; j++) {

                int temp;
                
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    temp = previous;
                } else {
                    temp = Math.min(
                        str1.charAt(i - 1) + dp[j],
                        str2.charAt(j - 1) + dp[j - 1]
                    );
                }
                
                previous = dp[j];
                dp[j] = temp;
            }
        }
        
        return dp[len2];
    }
}

The provided Java solution utilizes dynamic programming to solve the problem of finding the minimum ASCII deletion sum for two given strings. This approach helps to determine the minimal cost of removing characters from both strings such that they become identical, with the cost calculated based on the ASCII values of the characters removed.

Here's a more detailed explanation of the implementation:

• The function minDeletionCost takes two strings, str1 and str2, as parameters.
• To ensure that the first string is always the longer one, a check is performed at the beginning. If str1 is shorter than str2, the function recalls itself with swapped arguments.
• Two integer variables, len1 and len2, represent the lengths of str1 and str2 respectively.
• An integer array dp of size len2+1 is initialized to dynamically store intermediate results. Initially, the array builds up a cumulative sum of the ASCII values from str2.
• The outer loop iterates over each character in str1, while the inner loop does the same for str2.
• For each character comparison:
  • If the characters from str1 and str2 match, the current dp value is updated to the value before the comparison (previous).
  • If the characters do not match, the dp value is updated to the minimum sum after adding the ASCII value of the current character from either str1 or str2.
• After all iterations are complete, dp[len2] holds the result, which is the minimum deletion sum.

This approach ensures that each sub-problem is considered and that results are built up from previously computed values, leading to optimal solution discovery using dynamic programming principles. The space complexity is reduced to O(min(len1, len2)) by using a single-dimensional array.

int sumMinimumDeletes(char * str1, char * str2){

    // Swap if str1 is shorter than str2
    if (strlen(str1) < strlen(str2)) {
        return sumMinimumDeletes(str2, str1);
    }
    
    // For empty str1
    int len1 = strlen(str1), len2 = strlen(str2);
    int *dpRow = malloc((len2 + 1) * sizeof(int));
    dpRow[0] = 0;
    for (int j = 1; j <= len2; j++) {
        dpRow[j] = dpRow[j - 1] + str2[j - 1];
    }
    
    // Calculate necessary deletions row-by-row
    for (int i = 1; i <= len1; i++) {
        
        int prev = dpRow[0];
        dpRow[0] += str1[i - 1];
        
        for (int j = 1; j <= len2; j++) {

            int computedValue;
            
            // If characters match, use the diagonal value
            if (str1[i - 1] == str2[j - 1]) {
                computedValue = prev;
            }
            // Otherwise, choose the minimum of removing current characters from str1 or str2
            else {
                computedValue = fmin(
                    str1[i - 1] + dpRow[j],
                    str2[j - 1] + dpRow[j - 1]
                );
            }
            
            // Update prev to the current dpRow[j] for its use in the next iteration
            prev = dpRow[j];
            dpRow[j] = computedValue;
        }
    }
    
    // Returning the result
    return dpRow[len2];
}

This solution addresses the problem of finding the minimum ASCII delete sum for two strings using dynamic programming in C. Here's a closer look at how the code accomplishes this task:

• The code begins by examining the length of the strings, swapping them if the second string is shorter, ensuring that str1 is longer or of equal length to str2.

• Allocate space for a dynamic programming array dpRow, which represents the minimum delete sum for substrings up to the current indices of str1 and str2.

• Initialize dpRow[0] to zero. This serves as a base for the dynamic programming transition. dpRow[j] for j > 0 is progressively updated to hold the cumulative ASCII value sum up to that point for str2.

• The outer loop iterates over str1, and for each character, it updates the dynamic programming table. prev keeps track of the previous value that dpRow[j] held before its current update, which is essential for the DP transition.

• When characters of str1 and str2 at the current indices match, the diagonal value (prev) is used, indicating no deletion needed as they can be part of the common subsequence.

• When characters differ, the function chooses the minimum ASCII sum that results from deleting the current character either from str1 or str2.

• The computed values are updated in dpRow[j], and the iterating continues. By the end of the loops, dpRow[len2] contains the minimum ASCII delete sum for transforming str1 into str2. This result is then returned.

Ensure to include string.h and math.h headers in the C program for successful compilation and execution, as the functions strlen, malloc, and fmin are used. The approach ensures an efficient solution exploiting dynamic programming's overlapping subproblem and optimal substructure properties.

var totalDeleteASCII = function(str1, str2) {
    
    // Ensure str2 is the shorter of two strings
    if (str1.length < str2.length) {
        return totalDeleteASCII(str2, str1);
    }
    
    // Handle case where str1 is empty
    let len1 = str1.length, len2 = str2.length;
    let row = new Array(len2 + 1);
    row[0] = 0;
    for (let index = 1; index <= len2; index++) {
        row[index] = row[index - 1] + str2.charCodeAt(index - 1);
    }
    
    // Calculate result row by row
    for (let i = 1; i <= len1; i++) {
        
        let previous = row[0];
        row[0] += str1.charCodeAt(i - 1);
        
        for (let j = 1; j <= len2; j++) {

            let result;
            
            // If characters match, take top-left-diagonal value
            if (str1[i - 1] == str2[j - 1]) {
                result = previous;
            }
            
            // Else, find the minimum of deleting a character from either string
            else {
                result = Math.min(
                    str1.charCodeAt(i - 1) + row[j],
                    str2.charCodeAt(j - 1) + row[j - 1]
                );
            }
            
            // Store current row[j] in previous for next use before updating
            previous = row[j];
            row[j] = result;
        }
    }
    
    // Last element in row contains the final result
    return row[len2];
};

The JavaScript function totalDeleteASCII finds the minimum ASCII deletion sum for two input strings, str1 and str2. The function first checks that str2 is always the shorter string. If not, it swaps them. It then initializes a row array in which row[0] is set to 0 and populates it with cumulative ASCII values of the characters in str2.

The function proceeds with the calculation on a per-character basis for both strings using dynamic programming. For each character comparison:

• If the characters match, it assigns the value from the top-left diagonal of the previously processed values.
• If the characters don't match, it determines whether to delete a character from str1 or str2, choosing the option with the minimum ASCII cost.

The last element of the row array after processing both strings contains the resultant minimum ASCII deletion sum.

By using this approach:

• Ensure computational efficiency by avoiding re-calculations for previously compared and computed subsequences.
• Optimize memory usage by maintaining only a single row array throughout the computation instead of a full 2D array.

This solution for finding the minimum ASCII deletion sum for two strings effectively balances computational efficiency with memory usage, facilitating faster resolutions to problems involving string transformations.

class Solution:
    def minDeletionCost(self, string1: str, string2: str) -> int:
        
        # Make string2 the shorter one, if necessary
        if len(string1) < len(string2):
            return self.minDeletionCost(string1 = string2, string2 = string1)
        
        # Handling empty string1 case
        len1, len2 = len(string1), len(string2)
        current_row = [0] * (len2 + 1)
        for index in range(1, len2 + 1):
            current_row[index] = current_row[index - 1] + ord(string2[index - 1])
        
        # Calculate the minimum deletion cost row by row
        for i in range(1, len1 + 1):
            diagonal = current_row[0]
            current_row[0] += ord(string1[i - 1])

            for j in range(1, len2 + 1):
                if string1[i - 1] == string2[j - 1]:
                    result = diagonal
                else:
                    result = min(
                        ord(string1[i - 1]) + current_row[j],
                        ord(string2[j - 1]) + current_row[j - 1]
                    )
                
                diagonal = current_row[j]
                current_row[j] = result
        
        return current_row[-1]

The solution in Python provides a method to compute the minimum ASCII deletion sum for two strings. This algorithm ensures efficient handling of deletion costs using dynamic programming. Here’s how the solution is structured:

• The minDeletionCost function is executed with two string arguments, string1 and string2.

• It begins by ensuring that string2 is the shorter of the two strings. This is a preparatory step that potentially reduces the number of operations.

• An empty string case is covered by initializing len1 and len2 to the lengths of string1 and string2, respectively.

• A list current_row is initialized to store the cumulative ASCII values of string2 characters.

• The main double-loop constructs the table needed for the dynamic programming calculation:

  • The outer loop iterates through each character of string1.
  • The inner loop that goes through each character of string2, updating the current_row based on the minimum deletion cost calculated from the previous row’s values and the ASCII values of the current characters from both strings.
  • The deletion costs are properly minimized by checking if the characters of both strings match. If they do not, it adds the ASCII value of the current character from one string to the cumulated cost in current_row.

• At the end of the loops, the bottom-right value of the dynamic programming table (current_row[-1]) provides the necessary minimum ASCII deletion sum for transforming the two strings into a common string through deletions.

Regardless of the input strings, this dynamic programming approach ensures an optimal and efficient computation of the minimum deletion costs, resulting in a runtime complexity of O(m*n), where m and n are the lengths of the two strings.