A - atcoder < S Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

英小文字からなる文字列 S が与えられます． すぬけくんは，S の隣り合う 2 文字をスワップするという操作を行うことができます． 例えば，S=agc なら，1 回の操作で，S を gac (a と g をスワップ) もしくは acg (g と c をスワップ) に変換できます．

すぬけくんはこの操作を 0 回以上繰り返し， 辞書順で atcoder <S となるようにしたいです．

辞書順で x< y の定義

文字列 x,y が辞書順で x< y であるとは，以下のうちいずれかの条件を満たすことを意味します．

  • ある整数 i (1 \leq i \leq \mathrm{min}(|x|,|y|)) が存在して，x,y は先頭の i-1 文字が一致しており，かつ， x の i 文字目は y の i 文字目よりアルファベット順で真に小さい．
  • |x|< |y| であり，y の先頭の |x| 文字は x と等しい．

目標が達成可能かどうか判定し，可能な場合は必要な操作回数の最小値を求めてください．

1 つの入力ファイルにつき，T 個のテストケースを解いてください．

制約

  • 1 \leq T \leq 100
  • 1 \leq |S| \leq 1000
  • S は英小文字からなる文字列．

入力

入力は以下の形式で標準入力から与えられる． 入力の 1 行目は以下のとおりである．

T

そして，T 個のテストケースが続く． これらはそれぞれ以下の形式で与えられる．

S

出力

各テストケースについて，目標が達成不可能な場合は -1，可能な場合は必要な操作回数の最小値を出力せよ． 各テストケースごとに改行せよ．

入力例 1

3
atcodeer
codeforces
aaa

出力例 1

1
0
-1
  • 1 番目のテストケース: 例えば，末尾の 2 文字をスワップすることで，S=atcodere > atcoder となります．
  • 2 番目のテストケース: 操作を行うまでもなく，S=codeforces > atcoder です．
  • 3 番目のテストケース: どのように操作を行っても S> atcoder にはなりません．

Score : 300 points

Problem Statement

Given is a string S consisting of lowercase English letters. Snuke can do the operation of swapping two adjacent characters in S. For example, if S=agc, one operation can change it to gac (by swapping a and g) or acg (by swapping g and c).

Snuke wants to do this operation zero or more times so that atcoder <S holds lexicographically.

The definition of the lexicographic relation x< y

For strings x and y, it is said that x< y holds lexicographically if and only if one of the following conditions is satisfied:

  • There exists an integer i (1 \leq i \leq \mathrm{min}(|x|,|y|)) such that the first i-1 characters of x and those of y are equal and the i-th character of x is strictly smaller than that of y in alphabetical order.
  • |x|< |y| holds, and the first |x| characters of y are equal to x.

Determine whether the objective is achievable. If it is achievable, find the minimum number of operations needed.

Solve T test cases in an input file.

Constraints

  • 1 \leq T \leq 100
  • 1 \leq |S| \leq 1000
  • S is a string consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format. The first line of input is as follows:

T

Then, T test cases follow, each of which is in the following format:

S

Output

For each test case, print -1 if the objective is unachievable, and print the minimum number of operations needed if it is achievable. Use one line for each case.

Sample Input 1

3
atcodeer
codeforces
aaa

Sample Output 1

1
0
-1
  • The first test case: for example, swapping the last two characters makes S=atcodere > atcoder hold.
  • The second test case: before doing any operation, we already have S=codeforces > atcoder.
  • The third test case: no sequence of operations makes S> atcoder hold.