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