27534번 - 좋은 문자열 만들기

$0$과 $1$로 이루어진 길이 $n$의 이진 문자열 $a_1a_2...a_n$이 주어진다. 여러분은 비용 $1$로 하나의 문자를 다른 문자로 바꿀 수 있다.

좋은 이진 문자열은 다음을 만족하는 문자열이다.

• $0$과 $1$을 적어도 하나씩 포함한다.
• $0$을 포함하는 구간의 최소 길이는 $1$을 포함하는 구간의 최소 길이와 같다. 구간 [$s$, $e$]가 $j$를 포함한다는 것은 $a_i=j$인 모든 $i$에 대해 $s \leq i \leq e$가 성립한다는 것이다. ($1 \leq i \leq n$, $j=0$, $1$) 구간 [$s$, $e$]의 길이는 $e-s$로 정의한다.

주어진 문자열을 좋은 이진 문자열로 만드는 데 필요한 최소 비용을 구하시오.

첫째 줄에는 테스트케이스의 개수 $T$가 주어진다. ($1 \leq T \leq 10^3$)

각 테스트케이스는 다음과 같은 구성을 가진다.

첫째 줄에는 이진 문자열의 길이 $n$이 주어진다. ($1 \leq n \leq 10^6$)

다음 줄에는 $0$과 $1$로 이루어진 길이 $n$의 문자열이 주어진다.

모든 테스트케이스에 대해서 $n$의 합이 $10^6$ 이하임이 보장된다.

각 테스트 케이스에 대해서 주어진 문자열을 좋은 이진 문자열로 만들 수 없다면 $-1$을 출력한다. 좋은 이진 문자열로 만들 수 있다면 좋은 이진 문자열로 만들기 위한 최소 비용을 출력한다.