A small warehouse keeps its overflow shelf stocked with items, each stamped with a single lowercase category letter and arranged left to right in the order they were shelved. Every night the shelf undergoes one purge: for every distinct category currently present on the shelf, the purge removes that category's earliest (leftmost) remaining unit, while every other unit keeps its original relative order. Purges repeat night after night until the shelf is completely empty. Report the exact contents of the shelf, left to right, at the moment right before the very last purge is applied (the purge that finally empties it).
A single line containing the string s of lowercase English letters describing the shelf's initial contents, left to right.
A single line: the contents of the shelf immediately before the final purge, in left-to-right order.
1 <= |s| <= 1000 s consists only of lowercase English letters ('a'-'z').
Example 1
Input
aabcbbca
Expected
ba
Explanation
Counts: a=3, b=3, c=2, so the maximum frequency is 3 and the shelf empties after 3 nightly purges. Categories a and b (each frequency 3) survive through the last purge, each contributing exactly its final occurrence; c (frequency 2) is fully gone before then. The last occurrence of b comes before the last occurrence of a in the original string, so the shelf right before the final purge reads "ba".
Example 2
Input
aabbccddeeffgg
Expected
abcdefg
Explanation
Every one of the 7 categories appears exactly twice, so the maximum frequency is 2 and every category survives to the last purge with exactly its second (final) occurrence remaining. Listed in the order those final occurrences appear in the original string, the shelf right before the last purge reads "abcdefg".
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →