Minimum ASCII Delete Sum for Two Strings in Java
Given two strings s1, s2, find the lowest ASCII sum of deleted characters to make two strings equal.
Example 1:
Input:
s1 = "bea", s2 = "best"
Output: 328
Explanation: The ASCII value of "a" (97) is added to the total when "e" is removed from "bea". Eliminating "t" and "s" from "best" increases the total by 115+116 = 231. In the end, both strings equalize, and the smallest total that can make this happen is 97 + 231 = 328
Example 2:
Input:
s1 = "bae", s2 = "st"
Output: 527
Explanation: In this case, to make string every equal we have to delete every element. Accordingly, adding the ASCII values of "b","a" and "e" to "bae" after deleting "b","a" and "e". Thus, the sum will be 296 (98 + 97 + 101). Subtracting "t" and "s" from "st" raises the total to 115+116 = 231. Both strings are equal at the end, and the smallest total that can be reached to get there is 296 + 231 = 527.
BruteForce Approach
In this approach for solving the Minimum ASCII Delete Sum problem involves recursively evaluating every character deletion combination that could be made from
both input strings, trying out the ASCII delete sum for each combination, and then
choosing the lowest sum to guarantee thorough investigation of the possible
solutions.
FileName: MinimumASCIIDeleteSumBruteForce.java
import java.util.*;
public class MinimumASCIIDeleteSumBruteForce {
public static int minASCIIDeleteSum(String s1, String s2) {
return minASCIIDeleteSumHelper(s1, s2, 0, 0);
}
private static int minASCIIDeleteSumHelper(String s1, String s2, int i, int j) {
if (i == s1.length() && j == s2.length()) {
return 0;
} else if (i == s1.length()) {
int sum = 0;
for (int k = j; k < s2.length(); k++) {
sum += s2.charAt(k);
}
return sum;
} else if (j == s2.length()) {
int sum = 0;
for (int k = i; k < s1.length(); k++) {
sum += s1.charAt(k);
}
return sum;
} else if (s1.charAt(i) == s2.charAt(j)) {
// If characters match, move to next characters in both strings
return minASCIIDeleteSumHelper(s1, s2, i + 1, j + 1);
} else {
// If characters don't match, try deleting from both strings and find the minimum sum
int deleteFromS1 = s1.charAt(i) + minASCIIDeleteSumHelper(s1, s2, i + 1, j);
int deleteFromS2 = s2.charAt(j) + minASCIIDeleteSumHelper(s1, s2, i, j + 1);
return Math.min(deleteFromS1, deleteFromS2);
}
}
public static void main(String[] args) {
String s1 = "bea";
String s2 = "best";
System.out.println("Minimum ASCII Delete Sum: " + minASCIIDeleteSum(s1, s2));
}
}
Output:
Minimum ASCII Delete Sum: 328
Complexity Analysis:
Time Complexity: Exponential, O(2^(n+m)), where n and m are the lengths of the input strings. This is due to the algorithm's exponential time complexity, which arises from exploring every potential deletion combination.
Space Complexity: The input string lengths, n and m, determine the linear, O(n + m) space complexity. The recursive function call stack, which increases linearly with the lengths of the input strings, determines the space complexity.
Dynamic Programming Approach(Top-Down Memoization)
In dynamic programming approach with memoization to find the minimum ASCII delete sum for two given strings, s1 and s2. It recursively computes the minimum sum by considering all possible deletion combinations and memoizes results to avoid redundant computations and return the lowest ascii sum of deleted characters to make both strings equal.
FileName: MinimumASCIIDeleteSumMemoization.java
public class MinimumASCIIDeleteSumMemoization {
public static int minASCIIDeleteSum(String s1, String s2) {
Integer[][] memo = new Integer[s1.length() + 1][s2.length() + 1]; // Adjusted dimensions
return minASCIIDeleteSumHelper(s1, s2, 0, 0, memo);
}
private static int minASCIIDeleteSumHelper(String s1, String s2, int i, int j, Integer[][] memo) {
if (i == s1.length() && j == s2.length()) {
return 0;
}
// memoisation empty
if (memo[i][j] != null) {
return memo[i][j];
}
int result;
if (i == s1.length()) {
result = sumOfRemaining(s2, j);
} else if (j == s2.length()) {
result = sumOfRemaining(s1, i);
} else if (s1.charAt(i) == s2.charAt(j)) {
result = minASCIIDeleteSumHelper(s1, s2, i + 1, j + 1, memo);
} else {
int deleteFromS1 = s1.charAt(i) + minASCIIDeleteSumHelper(s1, s2, i + 1, j, memo);
int deleteFromS2 = s2.charAt(j) + minASCIIDeleteSumHelper(s1, s2, i, j + 1, memo);
// Minimum values from the string
result = Math.min(deleteFromS1, deleteFromS2);
}
memo[i][j] = result; // Memoize the result
return result;
}
private static int sumOfRemaining(String s, int start) {
int sum = 0;
for (int k = start; k < s.length(); k++) {
sum += s.charAt(k);
}
return sum;
}
public static void main(String[] args) {
String s1 = "bea";
String s2 = "best";
System.out.println("Minimum ASCII Delete Sum: " + minASCIIDeleteSum(s1, s2));
}
}
Output:
Minimum ASCII Delete Sum: 328
Complexity Analysis:
Time Complexity: O(n * m), where m denotes the string's length and n the string's length. This is due to the memoization approach's guarantee of a linear time complexity by solving each subproblem just once.
Space Complexity: O(n * m), where m denotes the string's length and n the string's length. The space complexity is increased by the size of the memoization array, which is n * m. Furthermore, the recursive stack space is bounded by n * m, the number of subproblems. The space complexity is linear overall.