Stringhalving
SRM 726 · 2017-12-18 · by subscriber
SRM 726 · 2017-12-18 · by subscriber · String Manipulation
Problem Statement
Problem Statement
Hero has a string of lowercase English letters.
Each letter that appears in the string appears exactly twice.
Hero now wants to remove one half of his string.
More precisely, he wants to remove one of the two copies of each letter in his string.
The order of the letters he does not remove will remain unchanged.
If there are multiple ways to remove the letters, Hero prefers the ones where the resulting string begins with a smaller letter (i.e., a letter that is earlier in the alphabet).
You are given the String s containing Hero's string.
Find the smallest letter that can appear at the beginning of the string after Hero removes half of the letters.
Return a String with a single character: that letter.
Constraints
- s will contain between 2 and 50 characters, inclusive.
- Each character in s will be between 'a' and 'z', inclusive.
- Each letter from 'a' to 'z' will have either zero or two occurrences in s.
Examples
0)
"baba" Returns: "a"
Hero can remove the first 'b' and the second 'a' to obtain the string "ab".
1)
"bbaa" Returns: "b"
Regardless of which 'a' and which 'b' Hero removes, the resulting string will always be "ba".
2)
"zyiggiyssz" Returns: "g"
3)
"topcodertpcder" Returns: "c"
4)
"rvofqorvfq" Returns: "f"
Submissions are judged against all 70 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class StringHalving with a public method string lexsmallest(string s) · 70 test cases · 2 s / 256 MB per case