A16640 | $Monocarp's String$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

Monocarp 有一个长度为 $n$ 的字符串 $s$，只包含字母 'a' 和 'b'。他想从字符串 $s$ 中删除一些（可能为零）连续的字母，使得剩余字符串中 'a' 和 'b' 的个数相等。Monocarp 可以从字符串 $s$ 的任意位置开始删除连续的字母。 Monocarp 非常喜欢他的字符串 $s$，因此他希望删除的连续字母数量尽可能少。 你的任务是确定，Monocarp 需要从字符串 $s$ 中删除的连续字母的最小数量，使得剩余字符串中 'a' 和 'b' 的数量相等。如果需要将字符串 $s$ 的所有字母都删除（即字符串变为空串），请输出 $-1$。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例包含两行： - 第一行包含一个整数 $n$（$2 \le n \le 2 \times 10^5$），表示字符串 $s$ 的长度； - 第二行包含一个长度为 $n$ 的字符串 $s$，只包含字母 'a' 和/或 'b'。 输入的额外限制：所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每组测试用例，输出如下结果： 如果为了使剩余字符串中 'a' 和 'b' 的数量相等，必须删除字符串 $s$ 的全部字母，输出 $-1$。 否则，输出 Monocarp 需要从字符串 $s$ 中删除的连续字母的最小数量，使得剩余字符串中 'a' 和 'b' 的数量相等。

输入 #1

5
5
bbbab
6
bbaaba
4
aaaa
12
aabbaaabbaab
5
aabaa

输出 #1

C++ 编辑器

输入

输出