Reorganize String

The problem. Given a string s of lowercase letters, rearrange its letters so that no two neighbours are the same. Return any such arrangement, or "" if it's impossible.

Example

s = "aab"     ->  "aba"
s = "aaab"    ->  ""        (impossible)
s = "vvvlo"   ->  "vlvov"   (any valid answer is fine)

When is it possible? The most frequent letter needs a gap after every copy but its last, so count copies need 2·count − 1 places. With n letters, that means count ≤ ⌈n / 2⌉ — and whenever that holds, an arrangement exists.