Consider a necklace composed of marbles of various colors arranged in a circle. The colors are represented by uppercase letters. We can describe a necklace with a string of characters as follows: start with any marble and go through all the marbles in either a clockwise or counter-clockwise direction, until the starting marble is reached again, meanwhile appending to the string the colors of the marbles in the order they are visited. Obviously, there could be many different strings describing the same necklace. For example, the necklace described by the string "CDAB" can also be described by seven other strings (see example 0).
You are given a String necklace containing the description of a necklace. Return the description for that necklace that comes earliest alphabetically.
|