← 返回题目列表

Codeforces · 2145/C

C. Monocarp 的绳子

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

Monocarp 有一个长度为 $$$n$$$ 的字符串 $$$s$$$,由字母 ' 组成a' 和 'b'。他想删除一些(可能是零) 连续 字符串中的字母以这样的方式表示字母数 ' 结果字符串中的a' 和 'b' 变得相等。 Monocarp 可以开始删除字符串 $$$s$$$ 中任意位置的字母。

Monocarp 非常喜欢他的字符串 $$$s$$$,因此他想从中删除尽可能少的连续字母。

您的任务是确定字符串 $$$s$$$ 中需要删除的连续字母的最小数量,以便字母数量 ' 结果字符串中的a' 和 'b' 变得相等。如果需要从字符串 $$$s$$$ 中删除所有字母(即,将其设为空),请报告此情况。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由两行组成:

  • 第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 字符串 $$$s$$$ 中的字符数;
  • 第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$,由字母 'a'和/或'b'.

对输入的附加约束:所有测试用例的 $$$n$$$ 值的总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印答案如下:

如果为了使字母数'a' 和 'b'相等,需要去掉字符串$$$s$$$中的所有字母,输出$$$-1$$$。

否则,输出 Monocarp 需要从字符串 $$$s$$$ 中删除的最小连续字母数,以便字母数 'a' 和 'b' 变得相等。

示例

输入
复制

5
5
bbbab
6
bbaaba
4
aaaa
12
aabbaaabbaab
5
aabaa

输出
复制

3
0
-1
2
-1

注意

在第一个示例中,Monocarp 需要删除字符串中的前三个字母。之后,他的字符串将变成“ab“。在这个字符串中,有一个字母 'a'和一个字母'b'.

在第二个示例中,给定的字符串包含三个字母 'a'和三个字母'b',所以不需要删除任何内容。

在第三个示例中,需要删除字符串的所有字母,因为没有字母 'b',因此应打印 $$$-1$$$。

在第四个示例中,Monocarp 可以从字符串中删除第五个和第六个字母。那么他的字符串将变成“阿巴巴巴“。该字符串中有五个字母 'a'和五个字母'b'.

在第五个示例中,需要删除字符串的所有字母,以使字母数 'a' 和 'b' 相等,因此应打印 $$$-1$$$。