Fewest Deletions to Make Two Equal
Delete characters from either string, in any number. Print the fewest deletions in total needed to make the two strings identical.
sea, eat -> 2 delete s from the first and t from the second, leaving ea
abc, abc -> 0 already equal
a, b -> 2 both must be emptied
## The reduction
Whatever survives is a subsequence of BOTH strings, since deletion is the only operation. Conversely any common subsequence can be reached by deleting everything else.
So the surviving string is a common subsequence, and the number of deletions is
(n - length of survivor) + (m - length of survivor) = n + m - 2 * survivor
Minimising deletions means maximising the survivor, which is the longest common subsequence of problem #237:
answer = n + m - 2 * LCS(a, b)
## The factor of two, which is the thing to get right
Each character NOT in the survivor is deleted once, from whichever string it sits in.
Summing over both strings gives n + m characters in total, of which 2 * LCS survive,
because the survivor is counted once in each string.
Writing n + m - LCS gives problem 511, the shortest common supersequence, which is a
different problem with a different answer on the same inputs. sea and eat give 2 here
and 4 there.
Having both problems in the bank next to each other is deliberate: they differ by one factor and the wrong one is not obviously wrong.
## Boundaries
a and b share nothing, so both are emptied and the answer is 2, the sum of the
lengths.
abc and abc are identical, so the answer is 0. Those two are the extremes and they
pin the formula down: a solution with the wrong factor gets one of them right.
aaa and aa answer 1: the shorter is already a subsequence of the longer, so only the
extra character goes.
ab and ba answer 2. The LCS is 1, either a or b, so one character goes from each
string. Not 0, which is what comparing sorted characters would suggest, and not 4.
## Cost
Time O(n m). Space O(m) with two rows, since only the previous row is read.