← 返回题目列表

Codeforces · 1905/C

C. 最大子序列

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

给定一个长度为 $$$n$$$ 的字符串 $$$s$$$。在一项操作中,您可以选择字符串 $$$s$$$ 的字典顺序最大的$$$^\dagger$$$ 子序列,并将其循环移位到右侧$$$^\ddagger$$$。

您的任务是计算 $$$s$$$ 排序所需的最少操作数,或者报告它永远不会达到排序状态。

$$$^\dagger$$$当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:

- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中的某个字母比 $$$b$$$ 中的对应字母更早出现。

$$$^\ddagger$$$通过将字符串 $$$t_1t_2\ldots t_m$$$ 向右循环移位,我们得到字符串 $$$t_mt_1\ldots t_{m-1}$$$。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 字符串 $$$s$$$ 的长度。

每个测试用例的第二行包含一个长度为$$$n$$$的字符串$$$s$$$,由小写英文字母组成。

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

输出

对于每个测试用例,输出一个整数 - 使 $$$s$$$ 排序所需的最少操作数,如果不可能,则输出 $$$-1$$$。

示例

输入 #1

6
5
aaabc
3
acb
3
bac
4
zbca
15
czddeneeeemigec
13
cdefmopqsvxzz

输出 #1

0
1
-1
2
6
0

注意

在第一个测试用例中,字符串 $$$s$$$ 已经排序,因此我们不需要任何操作。

在第二个测试用例中,执行一项操作,我们将选择 cb 并对其进行循环移位。字符串 $$$s$$$ 现在是已排序的 abc。

在第三个测试用例中,$$$s$$$ 无法排序。

在第四个测试用例中我们将执行以下操作:

- 字典顺序最大的子序列是 zca。那么 $$$s$$$ 就变成了 abzc。
- 字典顺序最大的子序列是 zc。那么 $$$s$$$ 就变成了 abcz。字符串已排序。

因此,我们需要 $$$2$$$ 操作。