Sort Characters By Frequency
Real-world version: Regroup The Sticker SheetThe statement here is our own: the same inputs, outputs and technique.
A print shop peels stickers off a sheet one after another and reads them out as a single string sheet. Each sticker carries one English letter or one digit. Upper case and lower case are different stock, so w and W are two unrelated stickers.
Lay the sheet out again so that all copies of a sticker sit next to each other in one unbroken block, and so that a block of a sticker peeled more often comes before a block of a sticker peeled less often. Every sticker from the original sheet appears in the answer, as many times as it was peeled.
When two stickers were peeled the same number of times, the one whose first copy appeared earlier in sheet gets the earlier block. That rule fixes a single correct answer, so return it as a string.
Examples
Example 1
- Input
- sheet = "mississippi"
- Output
- "iiiissssppm"
Both `i` and `s` were peeled four times, and the first `i` came before the first `s`, so the `i` block leads; then `p` with two and `m` with one.
Example 2
- Input
- sheet = "R2D2"
- Output
- "22RD"
The digit `2` was peeled twice so its block leads, and `R` and `D` tie at one each and keep the order in which they first showed up.
Example 3
- Input
- sheet = "aAbB"
- Output
- "aAbB"
All four stickers are distinct stock peeled once each, so the tie rule keeps the sheet exactly as it was read.
Constraints
- 1 <= sheet.length <= 5 * 10^5
- sheet consists of upper case English letters, lower case English letters and digits only.
- Letter case is significant: 'q' and 'Q' are different stickers.
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def regroup_stickers(sheet: str) -> str:public String regroupStickers(String sheet)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 11 test cases: 11 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's