Statistics

Problem Statement for "DyckwordUniformer"

Problem Statement

A Dyck word is a string consisting of n X's and n Y's (for some positive integer n) such that no initial segment of the string has more Y's than X's.

If we have a Dyck word we can swap any two consecutive substrings when both of them are Dyck words. It is easy to show that the result of this swap operation is a Dyck word too. For example, in "XXYXXYYY" (quotes for clarity) we can swap the substrings "XY" and "XXYY" to get "XXXYYXYY".

If a Dyck word A can be obtained from a Dyck word B using some number of the described swap operations they are called equivalent.

You will be given a String dyckword. Return the lexicographically smallest (i.e., the one that occurs first in alphabetical order) Dyck word that is equivalent with the given dyckword. Return "" (the empty string) if the given string is not a Dyck word.

Definition

Class:
DyckwordUniformer
Method:
uniform
Parameters:
String
Returns:
String
Method signature:
String uniform(String dyckword)
(be sure your method is public)

Constraints

  • dyckword will contain between 2 and 50 characters, inclusive.
  • Each character in dyckword will be either 'X' or 'Y'.

Examples

  1. "XXYXXYYY"

    Returns: "XXXYYXYY"

    The example from the problem statement.

  2. "XYXYXXXYYYXXYY"

    Returns: "XXXYYYXXYYXYXY"

    The result can be obtained by four swaps "XYXYXXXYYYXXYY" -> "XYXXXYYYXYXXYY" -> "XXXYYYXYXYXXYY" -> "XXXYYYXYXXYYXY" -> "XXXYYYXXYYXYXY".

  3. "XXXYYYXXYXXXYYYY"

    Returns: "XXXXYYYXYYXXXYYY"

    The result can be obtained by two swaps "XXXYYYXXYXXXYYYY" -> "XXXYYYXXXXYYYXYY" -> "XXXXYYYXYYXXXYYY".

  4. "XXYYYX"

    Returns: ""

  5. "XXXXXXXXXXXXXXXXXXXXXXXXXYYYYYYYYYYYYYYYYYYYYYYYYY"

    Returns: "XXXXXXXXXXXXXXXXXXXXXXXXXYYYYYYYYYYYYYYYYYYYYYYYYY"

  6. "XYXXXXXXXXXXXXXXXXXXXXXXXXYYYYYYYYYYYYYYYYYYYYYYYY"

    Returns: "XXXXXXXXXXXXXXXXXXXXXXXXYYYYYYYYYYYYYYYYYYYYYYYYXY"

  7. "XYXYXYXYXYXYXYXYXYXYXYXYXYXYXYXYXYXYXYXYXYXYXYXYXY"

    Returns: "XYXYXYXYXYXYXYXYXYXYXYXYXYXYXYXYXYXYXYXYXYXYXYXYXY"

  8. "XXYXXYYXYXXYYXYXXYYXYXXYYXYXXYYXYXXYYXYXXYYXYXXYYY"

    Returns: "XXXYYXXYYXXYYXXYYXXYYXXYYXXYYXXYYXYXYXYXYXYXYXYXYY"

  9. "XXYXXYYYXXYXXYYYXXYXXYYYXXYXXYYYXXYXXYYYXXYXXYYYXY"

    Returns: "XXXYYXYYXXXYYXYYXXXYYXYYXXXYYXYYXXXYYXYYXXXYYXYYXY"

  10. "XXYXXYYYXXXYYXXXYYYYXXXXYYYXXXXYYYYYXXYXXXXXYYYYYY"

    Returns: "XXXXXXYYYYYXYYXXXXXYYYYXXXYYYYXXXXYYYXXYYYXXXYYXYY"

  11. "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"

    Returns: ""

  12. "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY"

    Returns: ""

  13. "YX"

    Returns: ""

  14. "YYYYYYYYYYYYYYYYYYYYYYYYYXXXXXXXXXXXXXXXXXXXXXXXXX"

    Returns: ""

  15. "XXXXXXXXXXXXXXXXXXXXXXXXXYYYYYYYYYYYYYYYYYYYYYYYY"

    Returns: ""

  16. "XXXXXXXXXXXXXXXXXXXXXXXXYYYYYYYYYYYYYYYYYYYYYYYYY"

    Returns: ""

  17. "XXXXXXXXXXXXXXXXXXXXXXXXYYYYYYYYYYYYYYYYYYYYYYYYYX"

    Returns: ""

  18. "XXYXYYXXYY"

    Returns: "XXYXYYXXYY"

  19. "XYXXYYXYXXYXYYXYXXYYXXXYXYYYXXXYXYYXYXYYXXYY"

    Returns: "XXXYXYYXYXYYXXXYXYYYXXYXYYXXYYXXYYXXYYXYXYXY"

  20. "XXYXXYYXYXXYYXXYYY"

    Returns: "XXXYYXXYYXXYYXYXYY"

  21. "XXYY"

    Returns: "XXYY"

  22. "XY"

    Returns: "XY"

  23. "XYXXXYYYXXYXYXXXYXYYYXXYXYXYYXXYYXYXYXXYXYYY"

    Returns: "XXXXYXYYYXXYXYXYYXXYXYYXXYYXYXYXYXYYXXXYYYXY"

  24. "XXYXXYYYXXYXYYXYXYXYXXYYXXXYXYXYXYXYYXXYYY"

    Returns: "XXXYXYXYXYXYYXXYYYXXXYYXYYXXYXYYXXYYXYXYXY"

  25. "XYXYXYXXYYXYXYXYXYXXYYXYXYXYXXYYXYXYXXYXYYXYXY"

    Returns: "XXYXYYXXYYXXYYXXYYXYXYXYXYXYXYXYXYXYXYXYXYXYXY"

  26. "XYXXYXYYXXYXXYYYXYXXYXYYXXYYXYXY"

    Returns: "XXXYYXYYXXYXYYXXYXYYXXYYXYXYXYXY"

  27. "XXXXXYXYYXYXXYXYXYYYYXYXYXYXXXYYYXYXYXYXXYYXYY"

    Returns: "XXXXXYXYXYYXXYXYYXYYYXXXYYYXXYYXYXYXYXYXYXYXYY"

  28. "XYXYXXYYXXXYXYYY"

    Returns: "XXXYXYYYXXYYXYXY"

  29. "XXYYXYXXYXYYXYXYXXYYXXYXXYYXYXXYYYXXYYXYXXYXYY"

    Returns: "XXXYYXXYYXYXYYXXYXYYXXYXYYXXYYXXYYXXYYXYXYXYXY"

  30. "XYXXYYXYXY"

    Returns: "XXYYXYXYXY"

  31. "XXXXXXYYYXYXXYYXYXYYXXYXYXYXYYXYYYXXYXXYYY"

    Returns: "XXXXXXYYYXXYYXYXYXYYXXYXYXYXYYXYYYXXXYYXYY"

  32. "XYXXYXYXYXXYYY"

    Returns: "XXXYYXYXYXYYXY"

  33. "XXXYYY"

    Returns: "XXXYYY"

  34. "XYXYXYXYXYXYXYXXYXYXXYXYYXYXXYYY"

    Returns: "XXXYXYYXXYYXYXYXYYXYXYXYXYXYXYXY"

  35. "XXYYXXYYXYXXXXXXXYYYYYYXYXYXYXXYYY"

    Returns: "XXXXXXXYYYYYYXXYYXYXYXYYXXYYXXYYXY"

  36. "XXYYXYXXYXYXYYXYXXYY"

    Returns: "XXYXYXYYXXYYXXYYXYXY"

  37. "XXXYXYXYXYXYYXXYYXXYXYXYYY"

    Returns: "XXXYXYXYXYXYYXXYXYXYYXXYYY"

  38. "XXYXYXYXXYXYXYYXYYXXXYYYXXYYXYXY"

    Returns: "XXXYXYXYYXYXYXYXYYXXXYYYXXYYXYXY"

  39. "XXXXXYYXXYXYXYXYYXYXXYXXYYXYYXYYXYYY"

    Returns: "XXXXXXYYXYXYYXXYXYXYXYYXXYYXYXYYXYYY"

  40. "XYXYXYXXXYXYYXXYXXYYYYXYXXYXYXYYXYXY"

    Returns: "XXXXYYXYYXXYXYYYXXYXYXYYXYXYXYXYXYXY"

  41. "XXXXYYYXXYYXYXXYXYYXXYXYXYYXYXXYYY"

    Returns: "XXXXYYYXXYXYXYYXXYXYYXXYYXXYYXYXYY"

  42. "XYXYXXXYXYYXYYXXYYXYXYXXXYYYXXYXYXYXYXXXYXYYYXYY"

    Returns: "XXXXYXYYYXYXYXYXYXYYXXXYXYYXYYXXXYYYXXYYXYXYXYXY"

  43. "XXXXYYYYXXYYXXYXYYXYXYXXYYXYXYXXXXXYYYYXYY"

    Returns: "XXXXXYYYYXYYXXXXYYYYXXYXYYXXYYXXYYXYXYXYXY"

  44. "XYXXYYXYXXYYXXYYXYXYXXYXYXYXYXYXXYXXXYYYYY"

    Returns: "XXXXXYYYXYYXYXYXYXYXYYXXYYXXYYXXYYXYXYXYXY"

  45. "XXYYXXYYXXYYXXXXYXYXYYYXYXYXYYXYXYXXYYXXYXXYYXYY"

    Returns: "XXXXYXYXYYYXYXYXYYXXXYYXYXYYXXYYXXYYXXYYXXYYXYXY"

  46. "XYXXYXXXYYYXYXYYXYXXYYXXXXYYYXXYYXYXYY"

    Returns: "XXXXYYYXXYYXYXYYXXXXYYYXYXYXYYXXYYXYXY"

  47. "XYXYXYXXXYYYXYXXXYYXYXYXYXXYXYXYYXXXXYXYYYYY"

    Returns: "XXXXXYXYYYYXXYXYXYYXXYYXYXYXYYXXXYYYXYXYXYXY"

  48. "XYXYXXXYYXXYXYXYXYYXYXYYXYXYXYXY"

    Returns: "XXXYXYXYXYYXXYYXYXYYXYXYXYXYXYXY"

  49. "XXXXYYYXYYXXYYXXXYXXXXYXYYYYYY"

    Returns: "XXXXXXYXYYYYXYYYXXXXYYYXYYXXYY"

  50. "XYXYXYXYXXXYXYXXYYXYXYXXYXYYXYXYYXYY"

    Returns: "XXXXYXYYXXYYXYXYXYXYXYXYYXYYXYXYXYXY"

  51. "XYXYXXYXYXXXXYYXYYXYXYXYXYXYXYYXXYYXYXYXYY"

    Returns: "XXXXXYYXYYXYXYXYXYXYXYYXXYYXYXYXYXYXYYXYXY"

  52. "XYXXYXYXYXYXYXYXXYYXYXYXYXXYYXXXYYYYXXYXYXYY"

    Returns: "XXXXYYYXXYYXXYYXYXYXYXYXYXYXYXYXYYXXYXYXYYXY"

  53. "XXYXXYXYYXYXYYXXYXYXYXYYXYXXXYYYXXYXYXXYXYXYYY"

    Returns: "XXXYXYXYYXYXYYXXXYXYYXYXYXYYXXXYYYXXYXYXYXYYXY"

  54. "XXYXXYXYYXYXYXXXYXYXXYYYXYXYXXYYXXYXYXXYYYYY"

    Returns: "XXXXXYYXYXYYXXXYYXYXYYXXYYXYXYYXXYXYYXYXYXYY"

  55. "XXYXYXXXYYXYXYYXYXYXXYYXYXXYYXXYYXYXYXYYXXXYYXXYYY"

    Returns: "XXXXYYXYXYYXXYYXXYYXXYYXYXYXYXYXYXYXYXYYXXXYYXXYYY"

  56. "XXYYXYXXXYYXXYXXYXYYXXXYYXXYYYYY"

    Returns: "XXXXXYYXXYYYXXYXYYXYYXXYYYXXYYXY"

  57. "XYXXYYXYXYXXXXYYYXYXYXXYYXYXYXYY"

    Returns: "XXXXYYYXXYYXYXYXYXYXYYXXYYXYXYXY"

  58. "XXYXXYYYXXXXYYYXXXXYYYYYXXXYYXXXYYYYXXYXXXXXYYYYYY"

    Returns: "XXXXXXYYYYYXYYXXXXXYYYYXXXYYYYXXXXYYYXXYYYXXXYYXYY"

  59. "XY"

    Returns: "XY"

  60. "XXY"

    Returns: ""

  61. "XYY"

    Returns: ""

  62. "XYXY"

    Returns: "XYXY"

  63. "XXXYYYXYXXXXXYYYXXXYXYXXXYYXXYXXXYXYXYXYYYYYYXXYXY"

    Returns: ""

  64. "XXXXYY"

    Returns: ""

  65. "XYXXXY"

    Returns: ""

  66. "XXXXYYYXYYXXXYYYXXXXYYYXYYXXXYYYXXXXYYYXYYXXXYYYXY"

    Returns: "XXXXYYYXYYXXXXYYYXYYXXXXYYYXYYXXXYYYXXXYYYXXXYYYXY"

  67. "XXYYXXYYXXXXYYYYXYXYXYXYXYXYXYXYXYXYXYXYXYXYXXYXYY"

    Returns: "XXXXYYYYXXYXYYXXYYXXYYXYXYXYXYXYXYXYXYXYXYXYXYXYXY"

  68. "XXXY"

    Returns: ""

  69. "XXYXXYY"

    Returns: ""

  70. "XXXXYYYXXYXYXYYXXXYYYXXYXXYYYXXYXXYYYYXXYXYXXXYYYY"

    Returns: "XXXXYYXYYXXXYYXYYXXXYYYXXXYYYXXYXYXYYYXXXXYYYXYXYY"

  71. "XXXYYYXXYXXXYYYY"

    Returns: "XXXXYYYXYYXXXYYY"

  72. "XXXXXXXX"

    Returns: ""

  73. "XYXXYYXXXYYYXXYYXXXYYYXXYYXYXYXXYYXXXXYYYYXYXYXXYY"

    Returns: "XXXXYYYYXXXYYYXXXYYYXXYYXXYYXXYYXXYYXXYYXYXYXYXYXY"

  74. "XYXXY"

    Returns: ""

  75. "XX"

    Returns: ""

  76. "XXXYY"

    Returns: ""

  77. "YYXX"

    Returns: ""

  78. "XYXXYYXYXXYYXYXXYYXYXXYYXYXXYYXYXXYYXYXXYYXYXXYYXY"

    Returns: "XXYYXXYYXXYYXXYYXXYYXXYYXXYYXXYYXYXYXYXYXYXYXYXYXY"

  79. "XXXXYYYYXXYYXYXXYXYYXXXXYYYYXXYYXYXXYXYYXXXXYYYYXY"

    Returns: "XXXXYYYYXXXXYYYYXXXXYYYYXXYXYYXXYXYYXXYYXXYYXYXYXY"

  80. "XXYX"

    Returns: ""

  81. "XYXYXYXYXYXXXXXYYYYYXXXXYYYYXXXYYYXXYYXXYXYYXXYXYY"

    Returns: "XXXXXYYYYYXXXXYYYYXXXYYYXXYXYYXXYXYYXXYYXYXYXYXYXY"

  82. "XXXYX"

    Returns: ""

  83. "XXXYYYXXYXXXYYYYXYXYXXXYYYXXYYXYXYXXXYYYXXYYXXYY"

    Returns: "XXXXYYYXYYXXXYYYXXXYYYXXXYYYXXYYXXYYXXYYXYXYXYXY"

  84. "XXXXYYYY"

    Returns: "XXXXYYYY"

  85. "XYXXYYXXYXXYYYXYXYXYXYXYXYXYXYXYXYXXYYXXYYXXXYYY"

    Returns: "XXXYYXYYXXXYYYXXYYXXYYXXYYXYXYXYXYXYXYXYXYXYXYXY"

  86. "XYXXYYXXXYYYXXXXYYYYXXXXXYYYYYXXYXYYXXXYYXYYXXYXYY"

    Returns: "XXXXXYYYYYXXXXYYYYXXXYYXYYXXXYYYXXYXYYXXYXYYXXYYXY"

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: