0161MediumHash TableStringSortingHeap (Priority Queue)Bucket SortCounting

Regroup The Sticker Sheet

Tracked in this browser only

Trains the technique from

LeetCode 451Sort Characters By Frequency

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def regroup_stickers(sheet: str) -> str:

Java

public String regroupStickers(String sheet)

The intended approach

Time O(n + k log k) for n stickers and k distinct stickersSpace O(n)

One pass over the sheet records, for every distinct sticker, how many copies were peeled and the index of its first copy. Sorting the distinct stickers by descending count and, on a tie, ascending first index gives exactly the block order the statement demands, and each block is then just the sticker repeated by its count. At most 62 distinct stickers exist, so the sort is cheap next to the scan.

Pythonentry point: regroup_stickers

def regroup_stickers(sheet):
    # Time O(n + k log k): one scan to tally, then a sort over the k distinct
    # stickers (k is at most 62 here).
    # Space O(n): the tally is O(k), the assembled answer is O(n).
    tally = {}
    first_seen = {}
    for index, sticker in enumerate(sheet):
        if sticker not in tally:
            tally[sticker] = 0
            first_seen[sticker] = index
        tally[sticker] += 1
    order = sorted(tally, key=lambda s: (-tally[s], first_seen[s]))
    return "".join(s * tally[s] for s in order)

The obvious version

Repeatedly rescan whatever stickers are left, count each one by brute force, keep the most peeled sticker while preferring the earliest survivor on a tie, emit its whole block, and strip it out before the next round.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_regroup_stickers(sheet):
    remaining = list(sheet)
    blocks = []
    while remaining:
        chosen = remaining[0]
        chosen_count = remaining.count(chosen)
        for sticker in remaining:
            count = remaining.count(sticker)
            if count > chosen_count:
                chosen = sticker
                chosen_count = count
        blocks.append(chosen * chosen_count)
        remaining = [s for s in remaining if s != chosen]
    return "".join(blocks)

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in