Reorganize String

Problem

Given a string s of lowercase letters, rearrange its characters so that no two adjacent characters are the same. Return any such arrangement, or the empty string if none exists.

• The string is up to 600 characters.
• s consists of lowercase English letters only.

Examples

• s = "ccd" → "cdc". The two cs must be separated by the d.
• s = "cccd" → "". Three cs need at least two separators; only one other character exists.
• s = "wwwko" → "wkwow" (or another valid arrangement). Any arrangement with the three ws spread out is accepted.

Hints

1. Which character is the hardest to place? What is the maximum count it can have for a solution to exist at all?
2. At each step, place the character with the most remaining copies, unless it is the one you just placed. Why is "most remaining" the safe choice?
3. Max-heap of (count, char); pop the top, place it, and only push back the previous character after the current one is placed, so the same letter is never chosen twice in a row.