Statistics

Problem Statement for "CircleOrder"

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".

Definition

Class:
CircleOrder
Method:
firstOrder
Parameters:
String
Returns:
String
Method signature:
String firstOrder(String circle)
(be sure your method is public)

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

  1. "BACacb"

    Returns: "abc"

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

  2. "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'.

  3. "XYxPyp"

    Returns: "xyp"

  4. "BDAdCacb"

    Returns: "bdac"

  5. "abBcCdDeEfghFGHA"

    Returns: "abcdehgf"

  6. "BDdacAbC"

    Returns: "bcad"

  7. "acAC"

    Returns: "ac"

  8. "wXWBbx"

    Returns: "bwx"

  9. "cCdDeEFGfgHhIiJjKklLmnMNoOpPQqRr"

    Returns: "cdefghijklnmopqr"

  10. "CrcdDeEFGfgHhIiJjKklLmnMNoOpPQqR"

    Returns: "defghijklnmopqrc"

  11. "mnMNoOpPQqRCrcdDeEFGfgHhIiJjKklL"

    Returns: "defghijklnmopqrc"

  12. "aCbAcB"

    Returns: "NONE"

  13. "abCAcB"

    Returns: "cab"

  14. "DOGNAPHERZYLBCFIJKMQdognapherzylbcfijkmq"

    Returns: "dognapherzylbcfijkmq"

  15. "QOGNAPHERZYLBCFIJKMDqognapherzylbcfijkmd"

    Returns: "dmkjifcblyzrehpangoq"

  16. "DadAVvLl"

    Returns: "NONE"

  17. "ogGRUXsHDfqbuxAhOrBElwSWvaedLFQV"

    Returns: "NONE"

  18. "iGEecqVYCSdQPsgUpmuTMbBXvJjxyWItwD"

    Returns: "NONE"

  19. "uaKkEQftFNZRUqzTWwrOeonA"

    Returns: "NONE"

  20. "JpxUCruFQaloSjmiwGOtEAzZTPRIqeMfYLNyncHXhgsW"

    Returns: "NONE"

  21. "uPRJqBYfMeLQtdDlEhwkcsCVKUSmjrTzpNHyFnvWbZ"

    Returns: "NONE"

  22. "xTqKrGRtXEQekg"

    Returns: "NONE"

  23. "TmNPUjpqvnlBfVOioItZuWbQLARaJDMkFKrzcwdC"

    Returns: "NONE"

  24. "hmVlSsvLkMHK"

    Returns: "NONE"

  25. "yNkDWVZrBaKzpmGvbqJdYFQRPgjSiMufnsTUtwXxAI"

    Returns: "NONE"

  26. "cCdDeEfFgGiIjJmMoOqQrRtTuUvVwWxXyYzZ"

    Returns: "cdefgijmoqrtuvwxyz"

  27. "aAbBcCdDeEgGhHiIjJkKmMqQrRsStTuUwWyY"

    Returns: "abcdeghijkmqrstuwy"

  28. "bBhHiIlLmMnNpPqQrRtTuUvVwWzZ"

    Returns: "bhilmnpqrtuvwz"

  29. "KGhJjgIkiqHQ"

    Returns: "NONE"

  30. "uvVPpU"

    Returns: "puv"

  31. "ucCFUf"

    Returns: "cfu"

  32. "zoWmAFZMaOgwfG"

    Returns: "NONE"

  33. "UuPAsapRtTSgrG"

    Returns: "NONE"

  34. "LqQOFolf"

    Returns: "NONE"

  35. "iFkpzPZIKf"

    Returns: "NONE"

  36. "gQhZHzGq"

    Returns: "NONE"

  37. "zVAaZv"

    Returns: "NONE"

  38. "QprJZjiYIfPFqzRy"

    Returns: "NONE"

  39. "qILRgzZQOGojJril"

    Returns: "NONE"

  40. "EoOIeWiAaw"

    Returns: "NONE"

  41. "jYyboOJmBM"

    Returns: "NONE"

  42. "cNCGng"

    Returns: "NONE"

  43. "vAOElopLVIePai"

    Returns: "NONE"

  44. "uHULhl"

    Returns: "NONE"

  45. "XrSWRUmswzMZxu"

    Returns: "NONE"

  46. "kKiI"

    Returns: "ik"

  47. "kdSsJKjD"

    Returns: "jkds"

  48. "JpjSPs"

    Returns: "spj"

  49. "uHULlh"

    Returns: "luh"

  50. "XYxPypAabcBCdDeE"

    Returns: "acbdexyp"

  51. "BACacb"

    Returns: "abc"

  52. "AaBbCcDdEeFfGgHhJjKkLlPpOoIiUuYyTtRrWwQqZzXxVvNnMm"

    Returns: "abcdefghijklmnopqrtuvwxyz"

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: