Connection Status:
Competition Arena > DyckwordUniformer

DyckwordUniformer

SRM 274 · 2005-11-23 · by Andrew_Lazarev

SRM 274 · 2005-11-23 · by Andrew_Lazarev · Brute Force, Recursion, Sorting
Class Name: DyckwordUniformer
Return Type: String
Method Name: uniform
Arg Types: (string)
Problem Statement

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.

Constraints

  • dyckword will contain between 2 and 50 characters, inclusive.
  • Each character in dyckword will be either 'X' or 'Y'.
Examples
0)
"XXYXXYYY"
Returns: "XXXYYXYY"

The example from the problem statement.

1)
"XYXYXXXYYYXXYY"
Returns: "XXXYYYXXYYXYXY"

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

2)
"XXXYYYXXYXXXYYYY"
Returns: "XXXXYYYXYYXXXYYY"

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

3)
"XXYYYX"
Returns: ""
4)
"XXXXXXXXXXXXXXXXXXXXXXXXXYYYYYYYYYYYYYYYYYYYYYYYYY"
Returns: "XXXXXXXXXXXXXXXXXXXXXXXXXYYYYYYYYYYYYYYYYYYYYYYYYY"

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

Coding Area

Language: C++17 · define a public class DyckwordUniformer with a public method string uniform(string dyckword) · 86 test cases · 2 s / 256 MB per case

Submitting as anonymous