题目描述

给定一个长度为 $n$ 的字符串 $s$，仅由字符 'a' 和 'b' 组成。

每次操作，你可以选择一个位置 $i$（$1 \le i \le n-1$），交换相邻的字符 $s_i$ 和 $s_{i+1}$。

你需要用最少的操作次数，使得同一种字符（'a' 或 'b'）全部连续地排列在一起，形成恰好一个连续的块。

另一种字符可以在这个块的前面或后面，形成最多两个（可能为空）的块。

以下是一些合法的最终形式示例：

• 'aaabbbaaa' —— 所有的 'b' 连续在一起（一个块），'a' 可以在这个块前后；
• 'bbbaaaaaabbb' —— 所有的 'a' 连续在一起，'b' 则在字符串边缘；
• 'aaaaabbbb' 或 'bbbbaaaaa' —— 两种字符分别各自形成一个连续块。

你需要计算，实现上述目标状态所需的最小操作次数。

输入格式

输入包含若干组测试数据。

第一行输入一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的组数。

每组测试数据第一行输入一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示字符串 $s$ 的长度。

第二行输入一个仅包含字符 'a' 和 'b'，长度为 $n$ 的字符串 $s$。

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

输出格式

对于每组测试数据，输出一行一个整数，表示使同一种字符形成一个连续块所需的最小操作次数。

样例

5
4
abab
6
bababa
7
abababa
2
ab
1
b

1
2
2
0
0

样例说明

在第一个测试用例中，初始字符串为 'abab'：

• 交换相邻的第 $2$ 和 $3$ 个字符后，得到字符串 'aabb'；
• 或交换第 $1$ 和 $2$ 个字符后，得到字符串 'baab'。

两种情况下都只需操作一次，之后同一类字符已经连在一起，故最少操作次数为 $1$。

在第五个测试用例中，字符串仅包含一个字符 'b'。单个字符已经形成了连续块，不需要任何操作，输出 $0$。

由 ChatGPT 5 翻译

来源

Codeforces 2149D，英文题名 A and B。