Shortest String Containing Both
Print the LENGTH of the shortest string that contains both given strings as subsequences.
abac, cab -> 5 cabac contains both
abc, abc -> 3 the strings are equal
a, b -> 2 nothing is shared
## Two ways to see it, and they agree
Directly. Build the answer one character at a time. At each step either the two current characters agree, in which case one character serves both, or they differ, in which case one character serves one string and the other waits:
a[i] == b[j] -> 1 + f(i+1, j+1)
otherwise -> 1 + min( f(i+1, j), f(i, j+1) )
with base cases "one string is exhausted, so the rest of the other must be appended".
Via the shared part. Every character of the answer comes from a, from b, or from
both. The characters serving both form a common subsequence, and every common subsequence
can be arranged to be served that way. So
answer = n + m - (longest common subsequence of a and b)
Each shared character saves exactly one position, so saving the most means sharing the most.
The second view is shorter to write and reuses problem #237. The first is the one to reach for when the objective changes, because it does not depend on the saving being exactly one per shared character.
## Why the second view is worth checking rather than assuming
It rests on a claim: any common subsequence can be realised as the shared characters of some supersequence of that length. That is true, and it is the kind of step that is easy to assert and occasionally false in nearby problems.
Here it holds because a common subsequence gives an interleaving directly: walk both strings, emit shared characters once and unshared characters as they come.
Both formulations were computed independently and agreed on every test, which is the right way to be sure of a reduction like this.
## Boundaries
a and b share nothing, so the answer is 1 + 1 = 2, the sum of the lengths.
abc and abc are equal, so the answer is 3, not 6. That is the other extreme, where
the whole of both strings is shared.
aaa and aa answer 3: the shorter is already a subsequence of the longer, so the longer
IS the answer. A solution that adds lengths without subtracting the shared part gives 5.
## Cost
Time O(n m). Space O(n m), reducible to O(m) with two rows, since only the previous
row is read.