Problem Statement
Reorganize String
You are given a string s, and you need to shuffle its letters around so that no two letters that sit next to each other are the same. If there is no way to do that, you return an empty string. Here is the simple idea: the letter that shows up the most is the troublemaker, because it needs the most spacing. So at every step we place the most common letter we have left, as long as it is not the same as the letter we just placed. To always grab the most common letter quickly, we use a max-heap. A max-heap is like a vending machine that always hands you the biggest item first. You drop letters in with their counts, and it always gives back the one with the highest count. By keeping the most common letter on top and spacing it out, we avoid putting the same letter twice in a row.
Signals to notice
Brute force first
Try all permutations. Factorial. That direct path helps you understand the question, but it tends to treat every possibility as brand new instead of learning from earlier steps.
The key insight
Max-heap of (frequency, character). Always place the most frequent character that isn't the same as the last placed. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.
Trace it on s = "aab"
feasibility: freq={a:2,b:1}, max=2 ≤ (3+1)//2=2 → OK. heap=[(-2,'a'),(-1,'b')], result=[], prev=None
pop (-2,'a') → result="a"; prev=None (no push); remaining -1<0 → prev=(-1,'a'); heap=[(-1,'b')]
pop (-1,'b') → result="ab"; prev=(-1,'a') exists → push back, prev=None; remaining 0 ⇒ not<0 → no prev; heap=[(-1,'a')]
pop (-1,'a') → result="aba"; prev=None (no push); remaining 0 ⇒ not<0 → no prev; heap=[]
heap empty → return "aba"What must stay true
If the most frequent character appears more than (n+1)/2 times, rearrangement is impossible. Otherwise, alternating the two most frequent characters always works. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.
Shape of the loop
heap = max-heap of (-count, ch); prev = none
while heap not empty:
(count, ch) = pop most-frequent
append ch to result
if prev: push prev back; prev = none # re-enable last char now that 1 gap exists
if count+1 < 0: prev = (count+1, ch) # hold this char out one turn
return join(result)Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Not checking feasibility first — if any character has frequency > (n+1)/2, return empty string immediately. The fix is usually to return to the meaning of each move, not just the steps themselves.