Link here

I thought it should be Greedy at first, but was stuck in Example 2. Then, I considered about DP, but found it hard to figure out how to build the larger solution from the sub-problem.

So, another time I reached out for solution.

We use dp[i][j] to represent the minimum length of the first i letters after compression and after j deletions.

It obvious that if we delete the i-th letter, and then dp[i][j] = dp[i-1][j-1].

If we don’t, we can scan the former string sequence to try to “combine” the letters.

Link here

An excellent binary search problem. It’s easy to use brute-force or mergesort to solve it, but the time complexity is specified as $O(log(m+n))$ in the problem.

It’s obvious to think of binary search when noticing the time complexity with “log”, but constructing such a algorithm remains to be a big problem.

Here are three ways to solve the problem: