FoxAndHandle
SRM 563 · 2012-06-05 · by cgy4ever
SRM 563 · 2012-06-05 · by cgy4ever · Greedy, Simple Search, Iteration
Problem Statement
Problem Statement
We say that a string Z can be obtained by shuffling two strings X and Y together, if it is possible to interleave the letters of X and Y so that Z is obtained. It is not allowed to change the order of letters in X and Y.
For example, you can shuffle the strings X="abcd" and Y="efg" to produce any of the strings "abcdefg", "aebfcgd", "abcefgd", or "eabcfdg", but you cannot produce the string "bacdefg".
Formally, let Shuffle(X,Y) be the set of all strings that can be produced by shuffling X and Y together. We can define Shuffle inductively as follows:
Fox Ciel wants to register on TopCoder. In order to do that, she has to pick a handle. Ciel has a pet cat called S. As her handle, Ciel wants to use a string H with the following property: S can be obtained by shuffling H and some permutation of H together.
For example, if S="ceiiclel", one possible handle would be H="ciel": she can permute H to obtain H'="eicl", and then shuffle these H and H' together to produce S.
You are given theString S.
The constraints guarantee that there is at least one possible handle H with the above property.
Find and return the lexicographically smallest valid H.
Formally, let Shuffle(X,Y) be the set of all strings that can be produced by shuffling X and Y together. We can define Shuffle inductively as follows:
- for any string X: Shuffle("",X) = Shuffle(X,"") = { X }
- for any letters a, b and any strings X, Y: Shuffle(aX,bY) = { aZ : Z belongs to Shuffle(X,bY) } united with { bZ : Z belongs to Shuffle(aX,Y) }.
Fox Ciel wants to register on TopCoder. In order to do that, she has to pick a handle. Ciel has a pet cat called S. As her handle, Ciel wants to use a string H with the following property: S can be obtained by shuffling H and some permutation of H together.
For example, if S="ceiiclel", one possible handle would be H="ciel": she can permute H to obtain H'="eicl", and then shuffle these H and H' together to produce S.
You are given the
Constraints
- S will contain between 2 and 50 characters, inclusive.
- Each character of S will be a lowercase letter ('a'-'z').
- Each letter ('a'-'z') will occur in S an even number of times.
Examples
0)
"foxfox" Returns: "fox"
There are five possible handles for Fox Ciel in this test case: "fox", "fxo", "ofx", "oxf", and "xfo". The lexicographically smallest one is "fox".
1)
"ccieliel" Returns: "ceil"
Note that "ciel" is also a valid handle, but "ceil" is lexicographically smaller.
2)
"abaabbab" Returns: "aabb"
3)
"bbbbaaaa" Returns: "bbaa"
4)
"fedcbafedcba" Returns: "afedcb"
Submissions are judged against all 143 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class FoxAndHandle with a public method string lexSmallestName(string S) · 143 test cases · 2 s / 256 MB per case