MarbleNecklace

SRM 328 · 2006-11-29 · by _efer_

SRM 328 · 2006-11-29 · by _efer_ · Simple Search, Iteration, Sorting, String Manipulation

Show categories

Class Name: MarbleNecklace

Return Type: String

Method Name: normalize

Arg Types: (string)

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.

Constraints

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

Examples

"CDAB"
Returns: "ABCD"

This necklace can be described by the eight strings "CDAB", "DABC", "ABCD", "BCDA", "CBAD", "DCBA", "ADCB", "BADC". "ABCD" comes first lexicographically.

"RGB"
Returns: "BGR"

"TOPCODER"
Returns: "CODERTOP"

"X"
Returns: "X"

"TC"
Returns: "CT"

Submissions are judged against all 92 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MarbleNecklace with a public method string normalize(string necklace) · 92 test cases · 2 s / 256 MB per case