Minimum ASCII Delete Sum for Two Strings

Moderate
0/80
profile
Contributed by
0 upvote

Problem statement

You are given two strings, ‘str1’ and ‘str2’. Your task is to delete a few characters (possibly 0) from both strings to make the strings equal. The characters you delete must have the minimum possible sum of their ASCII values.

For Example: 
You are given str1=’abc’, str2=’bcd’, Here to make the string equal, we have to delete ‘a’ from str1 and ‘d’ from str2, which will add 97 and 100 to the answer. Hence the answer is 197
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains a single integer ‘t’ representing the number of test cases.

The first line of each test case contains a single string representing the string ‘str1.’

The second line of each test case contains a single string representing the string ‘str2.’
Output Format: 
For each test case, print a single integer representing the minimum sum of ASCII characters to delete to make both strings equal.

Print a separate line for each test case.
Note: 
You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.
Constraints: 
1 <= T <= 10
1 <= str1.size(), str2.size() <= 1000
Sample Input 1:
2
abc
bcd
aaab
aaa
Sample Output 1:
197
98
Explanation:
For the first test case, str1=’abc’, str2=’bcd’, Here to make the string equal, we have to delete ‘a’ from str1 and ‘d’ from str2, which will add 97 and 100 to the answer. Hence the answer is 197.

For the second test case, str1=’aaab’, str2=’aaa’, Here to make the string equal, we can only delete one character ‘b’ from str2, which has an ASCII value of 98. Hence the answer is 98.
Sample Input 2:
2
aaa
bbb
aa
aa
Sample Output 2:
585
0
Hint

Try to solve it recursively.

Approaches (3)
Brute Force(Recursion)

In this approach, we will check every possibility using recursion and get the minimum possible answer. Suppose we are at the ith and jth positions of ‘str1’ and ‘str2’ respectively. There can be only two possibilities. 

  1. If some ith and jth character matches, then we can reduce the ASCII sum if we include both ith and jth character in sequence, so we don't add their ASCII values.
  2. ith and jth character doesn't match, so we have two option for these
  3. skip ith character assuming jth character might be helpful later on, so we add ASCII of ith and recur for the rest.
  4. skip jth character assuming ith character might be helpful later on, so we add ASCII of ith and recur for the rest.

 

We create a recursive function, findMaxSum(str1, str2, i, j), where str1 and str2 are the strings we are checking and i and j are the indices of the strings.

We also create tillEndSum(str, index), which returns the ASCII sum from the index to the length of the string.
 

Algorithm:

  • In the tillEndSum(str, index),
    • Set sum as 0
    • Iterate i through every character of str starting from index till end
      • Add ASCII value str[i] to sum
    • Return sum
  • In the findMaxSum(str1, str2, i, j) function
    • If i and j are equal to the length of str1 and str2, respectively, we return 0
    • If i is equal to length of str1, return tillEndSum(str2, j)
    • If j is equal to length of str2, return tillEndSum(str1, i)
    • If str1[i] is equal to str2[j] return findMaxSum(str1, str2, i + 1, j + 1)
    • Return the minimum of findMaxSum(str1, str2, i + 1, j) + ASCII value of str1[i] and findMaxSum(str1, str2, i, j + 1) + ASCII value of str2[j]
  • In the main function
    • Return findMaxSum(str1, str2, 0, 0)
Time Complexity

O(N * (M ^ N)), Where ‘N’ and ‘M’ are the lengths of the strings given.

 

For each possible indices of both strings, we can have M ^ N possible states. There will be a total of N*(M ^ N) states. Hence the final time complexity is O(N*(M ^ N)).

Space Complexity

O(max(N, M)), Where N and M are the lengths of the strings given.

 

The space complexity of the recursion stack will be as much as the length of the largest of the two given strings.

Code Solution
(100% EXP penalty)
Minimum ASCII Delete Sum for Two Strings
Full screen
Console