Redirecting to
NADOS


  Prev   Next

MINIMUM ASCII DELETE SUM FOR 2 STRINGS







The best time to plant a tree was 20 years ago. The second best time is today

MINIMUM ASCII DELETE SUM FOR 2 STRINGS

Hey coder. In this article we will discuss a very interesting problem of Leetcode, "Minimum Ascii Delete Sum for 2 strings".

Be sure to have a clear mind before attempting this problem and try to go through the problem's outline once.


Important Links : Problem Link, Solution Video


Now let's go ahead and discuss the given problem.

Understanding the Problem:
  • You are given two strings S1 and S2.
  • You have to make these two strings equal by deleting characters. You can delete characters from any of the two strings.
  • The cost of deleting a character from any string is the ASCII value of that character.
  • You have to find the minimum ASCII sum of deleted characters.

In this problem, on removing some characters from s1 and s2 strings, say we achieve the strings s1' and s2', such that they are equal. The cost of making them equal is the sum of the ascii values of the deleted characters from both the strings (v1'+v2').

Similarly we find other modified strings which are made equal by deleting their characters. We calculate the cost for every pair of such strings. The minimum cost out of them is printed.

img

WHAT

We understand the approach by first discussing a formula. We consider f(s1,s2) as a function that takes 2 strings as input and returns the minimum cost to make them equal.

Now s1 and s2 can be written as c1r1 and c2r2 respectively where 'c' denotes the first character of a string and 'r' denotes the rest of the string.

We have 2 options, either c1=c2 or c1!=c2. The minimum cost for both these cases is given in figure 2.

img

We will learn why this formula works in later stages. Don't worry about it at the moment.

Now on the basis of the given formula, let's understand the following example.

Given, s1= "sea" and s2= "eat".

We make a tree for the given values by using the formula in figure 2.

In figure 3, we consider the numerator as the first string and the denominator as the second.

img

Starting from the base level, in strings "sea" and "eat" the first characters are not equal, therefore the formula for c1!=c2 is applied. On doing so, we get 2 options shown in level 1.

These 2 options further get solved. For "ea" and "eat", since the first characters are equal, therefore, we apply f(r1,r2) or f(a,at).

This process keeps following for the rest of the strings. When one of the strings is empty then we reach a base case, then the ascii value of the remaining string is returned as shown for the marked 't' in figure 3.

DYNAMIC PROGRAMMING

We will now learn how to solve this problem using dynamic programming.

STORAGE & MEANING

We make a 2D array for dimensions s1.length()+1 * s2.length()+1 as shown in figure 4.

img

The marked cell in figure 4 stores the minimum cost to equate the corresponding strings "ea" and "at".

TRAVERSE & SOLVE

To solve this array, we need to know the ascii values of all the characters used in the two strings which are given in figure 5.

img

  • Now, starting from the bottom right corner cell, the minimum cost to equate 2 blank strings is 0.
  • We solve the array for the last column. We are required to equate a blank string with a non-empty string. Hence, the total ascii value (sum of ascii values of all the characters) of the second string is stored in the respective cells.
    img
  • Similar to the last column, the last row is filled and we obtain figure 7.
    img
  • Now we need to equate the strings "a" and "t". Since the first characters are different, we have 2 options, either to remove 'a' or 't' using the formula.
    img
  • In figure 8, the left branch gives us the ascii value 97+116=213 and the right branch also gives us the ascii value 116+97=213. Hence, the minimum of these two is 213 which is stored in the cell.
    To solve this we make use of the values stored in the cells to the right and to the bottom of the current cell.
    img
  • Now, we move to the cell corresponding to "ea" and "t". Since the first characters are not equal, the two candidates are: ascii of 't'+ cell to the bottom=116+198= 314 and ascii of 'e'+ cell to the right=101+213=314. Here, the minimum value is 314.
    img
  • This process keeps repeating. We want you to fill this dp array for the rest of the values. If you have any difficulty, just refer to the solution video
  • At the end you must achieve a resultant array which looks like figure 11.
    img
  • Our final answer is stored in the top left corner for the strings "sea" and "eat". Hence, 231 is printed
import java.io.*; import java.util.*; public class Main { public static int solution(String s1, String s2) { int[][]dp=new int[s1.length()+1][s2.length()+1]; for(int i=dp.length-1;i>=0;i--){ for(int j=dp[0].length-1;j>=0;j--){ if(i==dp.length-1 && j==dp[0].length-1){ dp[i][j]=0; }else if(i==dp.length-1){ dp[i][j]=(int)s2.charAt(j)+ dp[i][j+1]; }else if(j==dp[0].length-1){ dp[i][j]=(int)s1.charAt(i)+ dp[i+1][j]; }else{ if(s1.charAt(i)==s2.charAt(j)){ dp[i][j]=dp[i+1][j+1]; }else{ dp[i][j]=Math.min(s1.charAt(i)+dp[i+1][j],s2.charAt(j)+dp[i][j+1]); } } } } return dp[0][0]; } public static void main(String[] args) { Scanner scn = new Scanner(System.in); String s1 = scn.next(); String s2 = scn.next(); System.out.println(solution(s1, s2)); } }
java; true";
Analysis
Time Complexity:

O(n2)

This time complexity is due to the use of nested loops.

Space Complexity:

O(n2)

Since an auxiliary space is required for the 2D dp array, therefore the space used is of order n*n.

CODE DISCUSSION

Now we need to discuss why the formula in figure 2 is used to implement the code of this program.

Meditate on the fact that by removing characters from strings, we obtain their subsequences and not their substrings.

We already know that the function f (s1,s2), takes 2 strings as input and returns the minimum cost to make them equal.

So to find this minimum cost, we list out all the possible subsequences obtained from string 1 which we call as set 1 and all possible subsequences obtained from string 2 which is called set 2.

We compare all subsequences in set 1 with that of s2 and locate all possible equal subsequences from the two sets. Then we find the sum of the ascii values of the deleted characters. The minimum sum is our answer.

img

The main objective of the above discussion is to understand that the minimum cost of the input strings depends on the Cartesian product of set 1 and set 2.

img

For a string "abc", its set can be represented as a sum of 2 sets of "bc" where a blank and a character "a" is put before the subsequences of the first set and second set respectively as shown in figure 14.

img

Hence figure 13 can be modified as shown below.

img

This essentially means that the 2 sets in every column given in figure 16 are compared with each other.

img

Or it can also be represented by figure 17.

img

From figure 17, we see that if c1=c2, then the minimum cost must lie in the 4th Cartesian product i.e. f(r1,r2). Else if c1!=c2, then the 4th Cartesian product can't contain the minimum cost.

To understand why it is so, we request you to watch the solution video .

Here we conclude the discussion of this problem. We hope you did not have any troubles understanding it.

Don't forget to check out the succeeding questions too. Goodbye.

Strings
Dynamic Programming and Greedy
Author: Shreeya Gupta
 
Run
Id Name