Making a Monochrome String

Let $C_0$ and $C_1$ be the number of $\texttt{0}$s and $\texttt{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 . Let the resulting array be , and let its total sum be . Then .

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$$