We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. 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 :
    image
    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:

  1. 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.
  2. In the second game, we rotate the suffix starting at index , so acab becomes aabc. Because the string is lexicographically smallest after one move, we print on a new line.

  3. In the third game, we perform the following moves:

    • Rotate the suffix starting at index (i.e., the entire string), so baba becomes abab.
    • Rotate the suffix starting at index , so abab becomes aabb.

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