CircleOrder

SRM 300 · 2006-04-27 · by dgoodman

SRM 300 · 2006-04-27 · by dgoodman · Greedy

Show categories

Class Name: CircleOrder

Return Type: String

Method Name: firstOrder

Arg Types: (string)

Problem Statement

We have a circular train track on which a number of loaded cars are located. Each car has its own specified unloading position on the track. The cars can be moved in either direction along the track, but cannot pass each other.

We want to specify the order in which the cars should be moved. The order of cars must allow each car to be moved just once all the way to its unloading position where it will remain.

The cars are each named with a lowercase letter, and their destinations with the same letter but in uppercase. The positions of the cars and of their destinations are given by a sequence of letters that is regarded as circular by wrapping around the ends. So, for example, "BACacb" describes a situation in which going clockwise around the track we encounter B, A, C, a, c, b, and then return back to B. Here there are 3 different orders in which the cars could be moved to their destinations: 'a' then 'c' then 'b', 'a' then 'b' then 'c', or 'b' then 'a' then 'c'.

Create a class CircleOrder that contains a method firstOrder that is given the original positions in a String circle and that returns the order in which they can be moved as a String, with the first character naming the first car to move, the second naming the second car, etc.

If there is more than one order possible, give the one that comes first alphabetically. If no order is possible, your method should return the 4-letter String "NONE".

Constraints

circle will contain between 2 and 50 characters, inclusive.
Each character will be a letter, 'a'-'z' or 'A'-'Z'.
No character will appear more than once.
If a letter appears in circle, it will appear both in uppercase and in lowercase.

Examples

"BACacb"
Returns: "abc"

This is the example given above. "abc" comes alphabetically before the other two choices, "acb" and "bac".

"ABCacb"
Returns: "NONE"

We cannot move car 'c' first. If we move 'a' first, then we can never move 'b' to 'B', but if we move 'b' first we can never move 'a' to 'A'.

"XYxPyp"
Returns: "xyp"

"BDAdCacb"
Returns: "bdac"

"abBcCdDeEfghFGHA"
Returns: "abcdehgf"

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

Coding Area

Language: C++17 · define a public class CircleOrder with a public method string firstOrder(string circle) · 52 test cases · 2 s / 256 MB per case