CF1905C Largest Subsequence

给定一个长度为 $n$ 的字符串 $s$。每次操作你可以选择字符串 $s$ 的字典序最大的子序列，并将其循环右移一次。 你的任务是计算将 $s$ 变为有序所需的最少操作次数，或者报告它永远无法达到有序状态。 $^\dagger$ 若字符串 $a$ 是字符串 $b$ 的前缀且 $a \ne b$，或者在第一个不同的位置上，$a$ 的字母在字母表中比 $b$ 的对应字母更靠前，则称字符串 $a$ 的字典序小于字符串 $b$。 $^\ddagger$ 将字符串 $t_1t_2\ldots t_m$ 循环右移一次，得到的字符串为 $t_m t_1 \ldots t_{m-1}$。

每组测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示字符串 $s$ 的长度。 每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，仅由小写英文字母组成。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示将 $s$ 变为有序所需的最少操作次数。如果不可能变为有序，输出 $-1$。

在第一个测试用例中，字符串 $s$ 已经有序，因此不需要任何操作。 在第二个测试用例中，进行一次操作，我们选择 cb 并将其循环右移。此时字符串 $s$ 变为 abc，已经有序。 在第三个测试用例中，$s$ 无法变为有序。 在第四个测试用例中，我们将执行如下操作： - 字典序最大的子序列是 zca。此时 $s$ 变为 abzc。 - 字典序最大的子序列是 zc。此时 $s$ 变为 abcz，字符串变为有序。 因此，需要 $2$ 次操作。 由 ChatGPT 4.1 翻译