Problem - Reorganize String

Rearrange a string so no two adjacent characters are the same. Return "" if impossible.

Example: "aab" becomes "aba". "aaab" is impossible. The core idea: if any character appears more than $(n+1)/2$ times, it is impossible. Tricky: you must alternate characters without repeating.

If the most frequent character has count $c$ and total length is $n$, you need at least $c-1$ other characters to separate them. The $(n+1)/2$ threshold comes from the pigeonhole principle.