단색 문자열 만들기

$\texttt{0}$의 개수와 $\texttt{1}$의 개수를 각각 $C_0, C_1$이라고 하자.

만약 $C_0=0$ 또는 $C_1=0$이면 문자열은 처음부터 단색이므로 답은 $0$이다.

만약 $C_0=C_1$이면 문자열 전체를 한 번에 삭제할 수 있으므로 답은 $1$이다.

이제 $C_0 \ne C_1$이고 두 문자가 모두 존재한다고 하자. 더 많이 등장하는 문자를 majority 문자라고 부르자. majority 문자를 $+1$, 나머지 문자를 로 바꾼 배열을 라고 하자. 전체 합을 라고 하면 이다.

삭제할 수 있는 부분 문자열은 정확히 합이 $0$인 구간이다. 따라서 어떤 연산을 여러 번 하더라도 전체 합 $D$는 변하지 않는다. 마지막 문자열은 단색이어야 하므로, 마지막에는 majority 문자만 정확히 $D$개 남아야 한다.

즉, 문제는 다음과 같이 바뀐다.

majority 문자 중 일부를 남기고, 나머지 문자들을 합이 $0$인 연속 구간들로 나누어 삭제한다. 이때 삭제하는 구간의 개수를 최소화한다.

prefix sum을 다음과 같이 정의하자.

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