CF2252B.Always Changing

You are given a binary string $s$ of length $n$.

A string is called alternating if no two adjacent characters are the same. For example, 0101, 1, and 01 are alternating, but 0110 is not.

You want to transform $s$ into an alternating string by performing the following operation any number of times (possibly zero):

• Choose any character currently in the string and delete it.

However, your sequence of operations must follow a rule: the characters you delete must strictly alternate. This means if the last character you deleted was 0, the next character you delete must be 1, and vice versa. Your very first deleted character can be either 0 or 1.

Find the minimum number of operations required to make $s$ an alternating string. If it is impossible to achieve this, output $-1$.

给你一个长度为 $n$ 的二进制字符串 $s$。

若一个字符串中任意两个相邻字符均不相同，则称其为交替字符串。例如，0101、1 和 01 是交替字符串，但 0110 不是。

你可以执行以下操作任意次（包括零次），以将 $s$ 变为一个交替字符串：

• 选择字符串中当前存在的任意一个字符并将其删除。

然而，你的操作序列必须满足如下规则：所删除的字符必须严格交替。也就是说，若你上一次删除的字符是 0，则下一次删除的字符必须是 1；反之亦然。第一次删除的字符可以是 0 或 1 中的任意一个。

求使 $s$ 成为交替字符串所需的最少操作次数。若无法实现，输出 $-1$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the string $s$.

The second line of each test case contains the binary string $s$ of length $n$, consisting only of the characters 0 and 1.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 字符串 $s$ 的长度。

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$，仅由字符 0 和 1 组成。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, output a single integer — the minimum number of operations required to make $s$ an alternating string, or $-1$ if it is impossible.

对于每个测试用例，输出一个整数——使 $s$ 变为交替字符串所需的最少操作次数；如果不可能，则输出 $-1$。

In the first test case, the string 0101 is already alternating. No operations are needed, so the answer is $0$.

In the second test case, the string is 111. To make it alternating, we must leave at most one 1, which requires deleting two 1s. However, our deletions must strictly alternate between 0 and 1. Since we have no 0s to delete, it is impossible to perform two deletions. The answer is $-1$.

In the third test case, the string is 100110. We can simply delete one 0 and one 1 to resolve the adjacent duplicates. Since we deleted exactly one 0 and one 1, the operations are perfectly balanced and valid. The remaining string is 1010, requiring exactly $2$ operations.

In the fourth test case, the string is 100010. To resolve the adjacent duplicates, we would naturally want to delete two 0s to form 1010. However, deleting two 0s and zero 1s violates the strict alternation rule (the difference in counts cannot exceed $1$). To fix this imbalance, we are forced to additionally delete a 1 from the edge of the string. We delete two 0s and one 1 (e.g., in the order 0, 1, 0), leaving the alternating string 010. This requires $3$ operations.

In the fifth test case, the string is 011110. Resolving the adjacent duplicates requires deleting three 1s. To balance this, we must additionally delete at least two 0s. Since our compressed string 010 only has two 0s (at its outer edges), we are forced to delete both of them, leaving a final string of just 1. We deleted three 1s and two 0s, which takes $5$ operations.

在第一个测试用例中，字符串 0101 已经是交替的，无需任何操作，因此答案为 $0$。

在第二个测试用例中，字符串为 111。为使其变为交替字符串，我们最多只能保留一个 1，即需删除两个 1。然而，我们的删除操作必须严格交替地在 0 和 1 之间进行。由于字符串中没有 0 可删，因此无法执行两次删除操作。答案为 $-1$。

在第三个测试用例中，字符串为 100110。我们只需删除一个 0 和一个 1，即可消除相邻重复字符。由于恰好删除了一个 0 和一个 1，操作完全平衡且合法。剩余字符串为 1010，共需 $2$ 次操作。

在第四个测试用例中，字符串为 100010。为消除相邻重复字符，我们自然希望删除两个 0，从而得到 1010。然而，删除两个 0 而不删除任何 1 违反了严格交替规则（两类字符删除数量之差不能超过 $1$）。为纠正这种不平衡，我们必须额外从字符串边缘删除一个 1。例如按 0, 1, 0 的顺序删除两个 0 和一个 1，最终剩下交替字符串 010。这需要 $3$ 次操作。

在第五个测试用例中，字符串为 011110。为消除相邻重复字符，需删除三个 1。为保持平衡，我们必须额外至少删除两个 0。由于其压缩字符串 010 仅在两端包含两个 0，我们被迫删除这两个 0，最终只剩下 1。我们共删除了三个 1 和两个 0，总共需要 $5$ 次操作。