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

Constraints - `1 ≤ length of a ≤ 1000` - `1 ≤ length of b ≤ 1000` - both contain only lowercase letters