Cheapest Deletions to Make Two Equal
Delete characters from either string to make the two identical. Deleting a character
costs its ASCII value, where a is 97 and z is 122. Print the smallest total cost.
sea, eat -> 231 delete s (115) and t (116)
delete, leet -> 403
a, b -> 195 97 + 98
## Why problem 516 does not transfer
Problem 516 counts deletions, so every character costs 1 and minimising the cost is maximising the number of survivors, which is the longest common subsequence.
Here characters cost different amounts. Keeping MORE characters is no longer automatically better: keeping one expensive character can beat keeping two cheap ones.
The tempting fix is to maximise the ASCII WEIGHT of the survivor instead of its length,
and that is in fact correct, since the total cost is
(sum of both strings) - 2 * (weight of the survivor). It is worth knowing the reduction
exists. But the direct minimisation is no longer code, so writing it directly is simpler
than proving the weighted version and then negating it.
## The grid
dp[i][j] = the smallest cost to make a[0..i-1] and b[0..j-1] identical
a[i-1] == b[j-1] -> dp[i][j] = dp[i-1][j-1] keep both, cost 0
otherwise -> dp[i][j] = min( dp[i-1][j] + cost(a[i-1]),
dp[i][j-1] + cost(b[j-1]) )
The matching case costs NOTHING, which is the difference from edit distance where a match also costs nothing but a mismatch has a replace option. There is no replace here, only delete, so a mismatch has exactly two branches.
## Both borders, not just one
dp[i][0] = dp[i-1][0] + cost(a[i-1]) empty the first string
dp[0][j] = dp[0][j-1] + cost(b[j-1]) empty the second
These are running SUMS, not zeros and not counts. Initialising them to 0, which is what a zero-filled array gives, says that emptying a string is free, and the answer comes out too small on every input where one string is longer.
That is the most common failure and it is silent. ab against abc answers 99, the cost
of the single c, and a zero border gives 0.
## Boundaries
abc and abc answer 0.
aa and a answer 97, one a deleted.
ab and ba answer 194, which is 97 + 97: the surviving character is a in one
reading or b in the other, and keeping b costs 97 + 97 while keeping a costs
98 + 98. So the cheaper choice keeps the MORE EXPENSIVE character, which is the whole
point of the problem and is the opposite of what counting would do.
az and za answer 194 for the same reason with a wider spread, and abc against cba
answers 390.
## Cost
Time O(n m). Space O(m) with two rows.