Making a Monochrome String

Let $C_0$ and $C_1$ be the number of $`0`$s and $`1`$s, respectively.

If $C_0=0$ or $C_1=0$, the string is already monochrome, so the answer is $0$.

If $C_0=C_1$, we can delete the whole string in one operation, so the answer is $1$.

Now assume $C_0 \ne C_1$ and both characters exist. Let the more frequent character be the majority character. Convert the majority character to $+1$ and the other character to $-1$. Let the resulting array be $A$, and let its total sum be $D$. Then $D>0$.

A deletable substring is exactly a substring with sum $0$. Therefore, no sequence of operations changes the total sum $D$. Since the final string must be monochrome, it must consist of exactly $D$ majority characters.

Thus, the problem becomes the following.

Keep some majority characters and divide all other characters into contiguous zero-sum segments. Minimize the number of deleted segments.

Define prefix sums as follows.

$$P_0 = 0,\qquad P_i = A_1 + A_2 + \cdots + A_i$$

A segment $(l+1,\ldots,r)$ has sum $0$ if and only if $P_l=P_r$.

Let $dp_i$ be the minimum number of operations needed after processing the first $i$ characters, where position $i$ is the current boundary. If the character at position $j+1$ is a majority character, we may keep it. Before keeping it, we may delete the segment from a previous boundary $i$ to position $j$, but only when $P_i=P_j$.

Maintain $best[x]$, the minimum $dp$ value among previous boundaries with prefix sum $x$. Then each transition can be processed in $O(1)$.

The total time complexity is $O(N)$, and the memory complexity is $O(N)$.