0121MediumHash TableStringGreedySortingHeap (Priority Queue)Counting

Paint Line Shuffle

Tracked in this browser only

Trains the technique from

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 paint line feeds car bodies through one spray booth. Every body queued for today carries a one-letter colour code, and the whole queue reaches you as the string codes. The booth has to stop and purge its nozzle whenever two bodies in a row ask for the same colour, so the shift lead wants the queue resequenced until no two neighbouring bodies share a code. You may put the bodies in any order you like, but you must send out exactly the bodies you were given, code for code.

Several orders usually avoid every purge, so build one specific order and return it: fill the queue from front to back, and at each slot send the code with the most bodies still waiting, skipping the code you placed in the slot before; when two or more codes have the same number of bodies waiting, send the one that comes earlier in the alphabet.

If no ordering can avoid a purge, return the empty string.

Examples

Example 1

Input: codes = "bbcbca"
Output: "bcbabc"

`b` starts with three bodies waiting, so it leads; then `c` with two beats `a` with one. At the fourth slot `a` and `c` each have one body left, and `a` wins the tie.

Example 2

Input: codes = "ccdc"
Output: ""

Three of the four bodies want `c`, and only one other body exists to separate them, so some pair of `c` bodies must end up adjacent.

Example 3

Input: codes = "ttssu"
Output: "ststu"

`s` and `t` both start with two bodies waiting, so the alphabet decides the first slot. The tie recurs at the third and fourth slots and is settled the same way, leaving the single `u` body last.

Constraints

1 <= codes.length <= 500
codes consists of lowercase English letters

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 paint_line_shuffle(codes: str) -> str:

Java

public String paintLineShuffle(String codes)

The intended approach

Time O(n log k) for n bodies over k distinct codes, k <= 26Space O(k) for the tallies and the priority queue, plus the answer

Tally the codes. If any single code has more bodies than the number of odd-numbered slots, `(n + 1) // 2`, the purges are unavoidable and the answer is empty. Otherwise keep the tallies in a priority queue ordered by bodies remaining, with the alphabet breaking ties, and pop the front each slot; if the popped code is the one just placed, take the next one instead and put the blocked code back. Pushing a code back only while bodies remain keeps the queue at most 26 entries.

Pythonentry point: paint_line_shuffle

def paint_line_shuffle(codes):
    import heapq
    tally = {}
    for ch in codes:
        tally[ch] = tally.get(ch, 0) + 1
    n = len(codes)
    if max(tally.values()) > (n + 1) // 2:
        return ""
    queue = [(-count, ch) for ch, count in tally.items()]
    heapq.heapify(queue)
    line = []
    while queue:
        neg, ch = heapq.heappop(queue)
        if line and line[-1] == ch:
            if not queue:
                return ""
            neg2, ch2 = heapq.heappop(queue)
            line.append(ch2)
            if neg2 + 1 < 0:
                heapq.heappush(queue, (neg2 + 1, ch2))
            heapq.heappush(queue, (neg, ch))
        else:
            line.append(ch)
            if neg + 1 < 0:
                heapq.heappush(queue, (neg + 1, ch))
    return "".join(line)

The obvious version

No priority queue and no feasibility formula: for each slot, rescan every code in alphabetical order to find the one with the most bodies left that is not the code just placed. If no code qualifies the line is stuck, which is exactly the unavoidable-purge case, so return empty. O(n * 26).

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_paint_line(codes):
    remaining = {}
    for ch in codes:
        remaining[ch] = remaining.get(ch, 0) + 1
    line = []
    for _ in range(len(codes)):
        pick = None
        for ch in sorted(remaining):
            if remaining[ch] == 0:
                continue
            if line and line[-1] == ch:
                continue
            if pick is None or remaining[ch] > remaining[pick]:
                pick = ch
        if pick is None:
            return ""
        line.append(pick)
        remaining[pick] -= 1
    return "".join(line)

How this problem was checked

Reference solution executed against 12 test cases — 12 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