Example
Input: s1 = "sea", s2 = "eat"
Output: 231
Explanation: Deleting "s" from "sea" adds the ASCII value of "s" (115) to the sum.
Deleting "t" from "eat" adds 116 to the sum.
At the end, both strings are equal, and 115 + 116 = 231 is the minimum sum possible to achieve this.
Solution
Recommended reading: LC 1143. Longest Common Subsequence
The question is pretty similar to the famous DP question, longest common subsequence and can be solved with slight modification. Instead of finding the longest common subsequence, we need to find the most “affordable” common subsequence of the two strings. The more the value of ASCII chars we have to delete, the less affordable is the common subsequence. Consider this example:
String 1: abcdef
String 2: defabc
These strings have two common subsequences of length 3 - "abc" and "def" but "def" is more affordable because we then have to only delete 2 a, 2 b and 2 c resulting in lower ASCII value of deleted characters.
So our aim is to find the longest common affordable subsequence. Define dp[i][j] as cost of string s1[0..i-1] and s2[0..j-1] where cost is the minimum sum of ASCII value of characters you’ll have to remove to make these strings equal (i.e. sum of value of ASCII characters not in the longest common affordable substring). When s1[i-1] = s2[j-1], dp[i][j] is simply equal to dp[i-1][j-1] since we do not need to remove any character. But when s1[i-1] != s2[j-1], dp[i][j] = min(dp[i-1][j] + s1[i-1], dp[i][j-1]+s2[j-1]); as we can delete s1[i-1] or s2[j-1]. The idea is similar to LC 1143. Longest Common Subsequence.
// Here dp[i][j] represents the characters we'll have to delete in the longest common affordable subsequence:
// "" e a t
// "" - e ea eat
// s s se sea seat
// e se s se set
// a sea sa s st
int minimumDeleteSum(string s1, string s2) {
int len1=s1.length(), len2 = s2.length();
vector<vector<int>> dp(len1+1, vector<int>(len2+1, 0));
for (int i=1; i<=len1; i++)
dp[i][0] = dp[i-1][0] + s1[i-1];
for (int j=1; j<=len2; j++)
dp[0][j] = dp[0][j-1] + s2[j-1];
for (int i=1; i<=len1; i++) {
for (int j=1; j<=len2; j++) {
if (s1[i-1] == s2[j-1])
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = min(dp[i-1][j] + s1[i-1], dp[i][j-1]+s2[j-1]);
}
}
return dp[len1][len2];
}
Time complexity: O(len1 * len2)
Space complexity: O(len1 * len2)