algoadvance

Leetcode 712. Minimum ASCII Delete Sum for Two Strings

Problem Statement

Given two strings s1 and s2, return the minimum ASCII delete sum for two strings such that the resulting two strings are equal.

Clarifying Questions

1. Input Constraints:
   • What is the maximum length for s1 and s2?
     • Up to 1000 characters each.
   • Are the characters limited to lowercase English alphabets?
     • It generally includes any printable ASCII character.
2. Edge Cases:
   • How do we handle empty strings?
     • If either s1 or s2 is empty, the cost will be the sum of ASCII values of the other string.
   • What should be returned if both strings are already equal?
     • Return 0 as no deletions are necessary.

Strategy

We’ll solve this problem using Dynamic Programming (DP). The idea is to use a 2D table where dp[i][j] represents the minimum ASCII deletion sum to make the substrings s1[0...i-1] and s2[0...j-1] equal.

DP Table Initialization:

• dp[0][0] = 0: No characters to delete when both substrings are empty.
• dp[i][0]: The sum of ASCII values of the first i characters of s1, representing deleting all characters from s1.
• dp[0][j]: The sum of ASCII values of the first j characters of s2, representing deleting all characters from s2.

DP Formula:

• If s1[i-1] == s2[j-1], then dp[i][j] = dp[i-1][j-1].
• If s1[i-1] != s2[j-1], then dp[i][j] = min(dp[i-1][j] + ASCII(s1[i-1]), dp[i][j-1] + ASCII(s2[j-1])).

Code

#include <vector>
#include <string>
#include <algorithm>

int minimumDeleteSum(std::string s1, std::string s2) {
    int m = s1.size();
    int n = s2.size();
    
    // Create a dp table 
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
    
    // Initialize the table
    for (int i = 1; i <= m; ++i) {
        dp[i][0] = dp[i-1][0] + s1[i-1];
    }
    for (int j = 1; j <= n; ++j) {
        dp[0][j] = dp[0][j-1] + s2[j-1];
    }
    
    // Fill the dp table
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (s1[i-1] == s2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = std::min(dp[i-1][j] + s1[i-1], dp[i][j-1] + s2[j-1]);
            }
        }
    }
    
    // The answer is in dp[m][n]
    return dp[m][n];
}

Time Complexity

The time complexity of this solution is O(m * n), where m is the length of string s1 and n is the length of string s2. This is because we fill up a DP table of size (m+1) x (n+1).

Space Complexity

The space complexity is also O(m * n) due to the storage required for the DP table.

By leveraging dynamic programming, we efficiently solve the problem in a reasonable time frame and memory usage given the constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?