Let us consider what strings can appear as an intermediate state, and minimize the number of positions where adjacent characters are different.

From an observation similar to the one in the writer’s explanation (the first one), we can see the following: consider what \(0\) or \(1\) in the initial state corresponds to what \(0\) or \(1\) in the final state. Then, for two characters whose relative order are different in the initial and final states, our string can have these characters in either order. Additionally, for two characters whose relative order are the same in the initial and final states, our string must have these characters in that order.

In the observation above, let us consider where each 1 can exist when the string is divided at 0s. The problem can be rephrased into finding the minimum cost when, after deciding which segment each 1 goes to, each segment with 1s incurs the following cost:

• 1 for a segment before the first 0 or after the last 0,
• 2 for other segments.

If all the weights are the same, the optimal solution can be obtained by sorting the segments by the right end and repeatedly putting a 1 to the back of a segment that does not have a 1 yet.

If we divide the problem into cases according to whether the first segment is used, the optimal solution for each case can be found similarly to the above.

The time complexity is \(\mathrm{O}(N)\) if properly implemented.