← 返回题目列表

AtCoder · agc048_a

A. 编码器 < S

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

分数: 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 按住。