- Prepare
- Algorithms
- Dynamic Programming
- Suffix Rotation

# Suffix Rotation

# Suffix Rotation

Megan is playing a string game with the following rules:

- It starts with a string, .
During each turn, she performs the following move:

- Choose an index in . The chosen index must be strictly greater than any index chosen in a prior move.
- Perform one or more circular rotations (in either direction) of the suffix starting at the chosen index.

For example, let's say

`abcdefjghi`

. During our move, we choose to do three right rotations of the suffix starting at index :

Note that this counts as*one*move.- The goal of the game is to convert into the lexicographically smallest possible string
*in as few moves as possible*. In other words, we want the characters to be in alphabetical order.

Megan plays this game times, starting with a new string each time. For each game, find the minimum number of moves necessary to convert into the lexicographically smallest string and print that number on a new line.

**Input Format**

The first line contains an integer, , denoting the number of games.

Each of the subsequent lines contains a single string denoting the initial value of string for a game.

**Constraints**

- consists of lowercase English alphabetic letters only.

**Output Format**

For each game, print an integer on a new line denoting the minimum number of moves required to convert into the lexicographically smallest string possible.

**Sample Input 0**

```
3
abcdefghij
acab
baba
```

**Sample Output 0**

```
0
1
2
```

**Explanation 0**

We play the following games:

- In the first game,
`abcdefghij`

is already as lexicographically small as possible (each sequential letter is in alphabetical order). Because we don't need to perform any moves, we print on a new line. - In the second game, we rotate the suffix starting at index , so
`a`

becomes**cab**`a`

. Because the string is lexicographically smallest after one move, we print on a new line.**abc** In the third game, we perform the following moves:

- Rotate the suffix starting at index (i.e., the entire string), so

becomes**baba**

.**abab** - Rotate the suffix starting at index , so
`a`

becomes**bab**`a`

.**abb**

Because the string is lexicographically smallest after two moves, we print on a new line.

- Rotate the suffix starting at index (i.e., the entire string), so