解题思路

1. 合法串等价于“至多发生一次字符切换”，即只可能是0...01...1或1...10...0（包含全0、全1退化情况）。
2. 枚举分界点k，计算两种形态代价：
   • 0...01...1：前缀中1的数量 + 后缀中0的数量；
   • 1...10...0：前缀中0的数量 + 后缀中1的数量。
3. 用前缀和维护前缀0/1个数，单个k可O(1)求值，整体O(n)。

复杂度分析

题目内容

给定一个只包含字符 $0$ 和 $1$ 的字符串。$Alice$ 不喜欢“$0$ 和 $1$ 交替”的样式，她认为“好看”的字符串必须满足：其所有 $0$ 字符（如果存在）形成一个连续的块，其所有 $1$ 字符（如果存在）也形成一个连续的块。

$Alice$ 可以进行若干次操作，每次操作可以把字符串中任意一个位置的字符改成 $0$ 或 $1$。

请你计算：把给定的字符串变为“好看”需要的最少操作次数。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T\ (1 \le T \le 10^5)$ 表示测试组数。随后每组数据包含：

• 第一行输入一个整数 $n\ (1 \le n \le 2 \times 10^5)$，表示字符串长度；
• 第二行输入一个长度为 $n$ 的仅由 $0$ 和 $1$ 组成的字符串。

保证所有测试中 $n$ 的总和不超过 $4 \times 10^5$。

输出描述

对于每组数据，输出一个整数，表示把字符串变为“好看”所需的最少操作次数。

样例1

输入

3
5
01010
4
1111
7
1011000

输出

2
0
1

说明

• 样例 $1$：将位置 $2$ 的 $1$ 改为 $0$，将位置 $4$ 的 $1$ 改为 $0$，得到 "$00000$" 或将两处 $0$ 改为 $1$ 得到 "$11110$"，最少 $2$ 次。
• 样例 $2$：原串已好看（全为 $1$），无需操作。
• 样例 $3$：把位置 $2$ 的 $0$ 改成 $1$，得到 "$1111000$"，最少 $1$ 次。