Reorganize String
Rearrange a string so that no two adjacent characters are the same, or return an empty string if that is impossible.
Open on LeetCode ↗Intuition
The natural greedy move is: pop the most frequent character off a max-heap, append it, decrement, push it back. Run that on 'aab' and watch it fail — you emit 'a', push 'a' back with count 1, and 'a' is still the maximum, so you emit 'a' again and produce 'aa'. The character you just placed comes straight back to the top, which is precisely the character you are forbidden from placing next. The fix is to pop TWO each round and place them together. The second character is not a bonus, it is the separator: by the time the first one returns to the heap, something else has already occupied the slot beside it. Before any of that, check feasibility in one line — a string of length L has only (L+1)//2 alternating slots, so if any frequency exceeds that, no arrangement exists at all and you return '' immediately. The invariant is that the character appended in one round is never the character appended immediately before it, because those two came from a single pop-pair and were distinct by construction.
Always place the two most frequent remaining characters next — they can't be equal to each other, so no adjacency is created. The feasibility guard is exact: if any character exceeds (len + 1) / 2, the pigeonhole principle makes a valid arrangement impossible.
Approach
Reject the impossible case up front
Count the characters. In a valid answer of length L, any single character can occupy at most every other position, and there are (L+1)//2 such positions counting from index 0. If the maximum frequency exceeds that, two copies must end up adjacent no matter how you arrange the rest — return the empty string without building anything. This check is what makes the rest of the algorithm total: past it, a valid arrangement is guaranteed to exist.
Pop two, place two
Push (-count, char) pairs into heapq to get a max-heap. Each round, pop the two most frequent characters and append both to the result in that order. Popping one is the bug — the same character stays maximal and immediately reappears. Popping two guarantees the pair is distinct, so no adjacency violation is created inside the round, and the first one is separated from its own next copy by the second.
Push back only what still has work, then handle the tail
Decrement both counts and push back any that remain positive. The loop runs while at least two entries remain. When exactly one is left, its count must be 1 — a larger count would have failed the feasibility check — so append it and finish. It cannot clash with the last character placed, because that character was popped and pushed back in a round where this one was not the partner.
Solution & live demo
Common pitfalls
Getting the feasibility bound wrong
if max(freq.values()) > len(s) // 2:
if max(freq.values()) > (len(s) + 1) // 2:
An odd-length string can accommodate one extra of the dominant character — "aba" is valid with two a's in a string of length 3. Using plain floor division rejects solvable inputs.
Popping one character at a time
c1, ch1 = heappop(heap) out.append(ch1) heappush(heap, (c1 + 1, ch1))
c1, ch1 = heappop(heap) c2, ch2 = heappop(heap)
Popping singly returns the same character immediately, since it may still be the most frequent — producing an adjacent repeat. Holding two out at once guarantees the next placement differs.
Pushing back a character with zero remaining
heapq.heappush(heap, (c1 + 1, ch1))
if c1 + 1 < 0:
heapq.heappush(heap, (c1 + 1, ch1))With negated counts, c1 + 1 == 0 means the character is exhausted. Pushing it back re-emits a character that has already been fully placed, corrupting both the output and the length.
Edge cases
The heap holds one entry, the loop body never runs, and the tail branch emits 'a' — trivially valid.
max frequency 3 exceeds (4+1)//2 = 2, so the guard returns '' before the heap is ever touched.
frequency 2 equals (3+1)//2 = 2, so it is feasible; the pop-two loop produces 'aba'.
The final single entry has count 1 and is appended at the end, which is the only position where a lone character can never create an adjacency.