# 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.