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.
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
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.