分数: 300 点
问题陈述
给定的是一个字符串 S 由小写英文字母组成。
Snuke可以进行两个交换的操作 相邻 中的字符 S。
例如,如果 S=agc,一次操作即可将其更改为 gac (通过交换 a 和 g)或 acg (通过交换 g 和 c).
Snuke 想要执行此操作零次或多次,以便 atcoder <S 按字典顺序成立。
字典顺序关系的定义 x< y
对于字符串 x 和 y,据说 当且仅当满足以下条件之一时, x< y 按字典顺序成立:
- 存在一个整数 i (1 \leq i \leq \mathrm{min}(|x|,|y|))使得第一个 i-1 的字符 x 以及 y 相等并且 i- 第一个字符 x 严格小于 y 按字母顺序排列。
- |x|< |y| 成立,并且第一个 |x| 的字符 y 等于 x.
确定目标是否可以实现。如果可以实现,找出所需的最少操作数。 输入文件中的
解决 T 测试用例。
约束
- 1 \leq T \leq 100
- 1 \leq |S| \leq 1000
- S 是由小写英文字母组成的字符串。
输入
输入由标准输入按以下格式给出。 第一行输入如下:
T
然后, T 测试用例如下,每个测试用例的格式如下:
S
输出
对于每个测试用例,打印 -1 如果目标无法实现,则打印所需的最少操作数(如果可以实现)。 每种情况使用一行。
示例输入 1
3 atcodeer codeforces aaa
示例输出 1
1 0 -1
- 第一个测试用例:例如,交换最后两个字符使得 S=
atcodere>atcoder按住。 - 第二个测试用例:在进行任何操作之前,我们已经有 S=
codeforces>atcoder. - 第三个测试用例:没有操作序列使得 S>
atcoder按住。