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.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Suffix Rotation

Suffix Rotation

Problem
Submissions
Leaderboard
Discussions
Editorial

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.

Author

forthright48

Difficulty

Expert

Max Score

80

Submitted By

608

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature