CF2252B Always Changing

给定一个长度为 $n$ 的二进制字符串 $s$。 如果一个字符串中没有两个相邻的字符相同，则称其为交错（alternating）字符串。例如 0101、1 和 01 都是交错的，但 0110 不是。 你可以通过任意次数（可以为零）执行以下操作，将 $s$ 变为交错串： - 每次选择当前字符串中的任意一个字符并将其删除。 但操作必须遵守如下规则：你删除的字符必须严格交错。也就是说，如果你上一次删除的是 0，则下一个必须删除 1，反之亦然。你第一次删除的字符可以是 0 也可以是 1。 请你计算将 $s$ 变为交错字符串所需的最小操作次数。如果无法实现，输出 $-1$。

每组测试包含多个测试用例。第一行输入测试用例个数 $t$（$1 \le t \le 10^4$）。 接下来按照如下格式描述每组测试用例： 每组测试用例的第一行输入一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示字符串 $s$ 的长度。 第二行输入一个只包含 $0$ 和 $1$ 的二进制字符串 $s$，长度为 $n$。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

每组测试用例输出一行，一个整数，表示最少需要多少次操作才能将 $s$ 变为交错字符串。如果无法实现，则输出 $-1$。

在第一个测试用例中，字符串 0101 已经是交错的，不需要任何操作，答案为 $0$。 在第二个测试用例中，字符串为 111。要将其变为交错的，最多只能保留一个 1，需要删除两个 1。但删除操作必须严格交错，由于没有 0 可删，无法做到多次交错删除，答案为 $-1$。 在第三个测试用例中，字符串为 100110。我们可以分别删除一个 0 和一个 1，解决相邻重复字符问题。由于恰好各删一次 0 和 1，操作正好交错且有效。剩下的字符串变为 1010，仅需 $2$ 次操作。 在第四个测试用例中，字符串为 100010。若想去重构成 1010，自然愿望是删掉两个 0，但这样做违反了操作必须交错的规则（操作数目差不能超过 $1$）。因此被迫还需额外从两端删掉一个 1。比如删去两个 0 和一个 1（比如依次删 0、1、0），剩下字符串为 010，需要 $3$ 次操作。 在第五个测试用例中，字符串为 011110。要去掉三个 1，解决相邻重复问题，为此至少还要删掉两个 0 以满足交错要求。结果删去三个 1 和两个 0，字符串只剩 1，总共需要 $5$ 次操作。 由 ChatGPT 5 翻译