Last Updated: 14 Jan, 2022
Minimum ASCII Delete Sum for Two Strings
Moderate
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
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
Approaches
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.
- 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.
- ith and jth character doesn't match, so we have two option for these
- skip ith character assuming jth character might be helpful later on, so we add ASCII of ith and recur for the rest.
- 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)
In this approach, we will do the same as the previous approach, but this time we will create a cache to store the result of each state in the recursive function so that it does not recalculate each time.
We create a recursive function, findMaxSum(str1, str2, i, j, cache), where str1 and str2 are the strings we are checking and i and j are the indices of the strings. ‘Cache’ is the cache of states.
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, cache) 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 cache[i][j] is not equal to -1 return cache[i][j]
- If str1[i] is equal to str2[j] , set cache[i][j] as findMaxSum(str1, str2, i + 1, j + 1) and return it.
- Set cache[i][j] as 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] and return it.
- In the main function
- Create a 2D matrix cache of the length of str1 x length of str2 dimensions and set it as -1.
- Return findMaxSum(str1, str2, 0, 0, cache)
In this approach, we will try to build a solution with dynamic programming using bottom-up. We will create a dp table where dp[i][j] will represent the minimum ASCII delete sum till the ith and jth index of str1 and str2, respectively.
Therefore from the above two approaches we can conclude that
if str[i] == str[2] dp[i][j] = dp[i - 1][j - 1] if not, d[i][j] is minimum(dp[i - 1][j] + str1[i - 1], dp[i][j - 1] + str2[j - 1]), We use i - 1 and j - 1 as char index to accommodate for 0 length string.
Algorithm:
- Set N and M as the lengths of str1 and str2
- Create a 2D array of NxM length filled with 0
- Iterate i from 1 to N and set dp[i][0] = str1[i - 1] + dp[i - 1][0]
- Iterate i from 1 to M and set dp[0][i] = str2[i - 1] + dp[0][i - 1]
- Iterate i from 1 to N
- Iterate j from 1 to M
- If str1[i - 1] is equal to str2[j - 1] set dp[i][j] as dp[i - 1][j - 1]
- Otherwise set dp[i][j] as minimum of dp[i][j - 1] + str2[j - 1] and dp[i - 1][j] - str1[i - 1]
- Iterate j from 1 to M
- Return dp[N][M]
Similar problems