TopCoder problem "MarbleNecklace" used in SRM 328 (Division II Level One)



Problem Statement

    

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.

 

Definition

    
Class:MarbleNecklace
Method:normalize
Parameters:String
Returns:String
Method signature:String normalize(String necklace)
(be sure your method is public)
    
 

Constraints

-necklace will contain between 1 and 50 characters, inclusive.
-Each character of necklace will be an uppercase letter ('A'-'Z').
 

Examples

0)
    
"CDAB"
Returns: "ABCD"
This necklace can be described by the eight strings "CDAB", "DABC", "ABCD", "BCDA", "CBAD", "DCBA", "ADCB", "BADC". "ABCD" comes first lexicographically.
1)
    
"RGB"
Returns: "BGR"
2)
    
"TOPCODER"
Returns: "CODERTOP"
3)
    
"SONBZELGFEQMSULZCNPJODOWPEWLHJFOEW"
Returns: "BNOSWEOFJHLWEPWODOJPNCZLUSMQEFGLEZ"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6855

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10008&pm=6855

Writer:

_efer_

Testers:

PabloGilberto , brett1479 , Olexiy , lovro

Problem categories:

Simple Search, Iteration, Sorting, String Manipulation