← 返回题目列表

Codeforces · 2149/D

D. A 和 B

中文机器翻译题面 查看原题

给定一个长度为 $$$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 \cdot 10^5$$$) — 字符串 $$$s$$$ 的长度。

第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$,仅包含字符 'a' 和 'b'.

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

输出

对于每个测试用例,输出一个整数——两种类型之一的所有字符形成单个连续块所需的最小操作数。

示例

输入
复制

5
4
abab
6
bababa
7
abababa
2
ab
1
b

输出
复制

1
2
2
0
0

注意

在第一个测试用例中,初始字符串是 'abab':

  • 通过交换位置 $$$2$$$ 和 $$$3$$$ 处的相邻字符,我们得到字符串 'aabb';
  • 或者通过交换位置 $$$1$$$ 和 $$$2$$$ 处的字符,我们得到字符串 '咩咩'.
在这两种情况下,只执行一次操作,之后一种类型的所有字母形成一个块,因此最少操作次数为 $$$1$$$。

在第五个输入测试用例中,字符串由单个字符 ' 组成b'。单个字符已经形成一个连续的块,不需要交换,所以最少的操作次数是$$$0$$$。