Reorganize String

medium

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

Return any possible rearrangement of s, or return "" if it is not possible.

Test Cases

Copy an input into the main harness and Run to verify

Input

s = "aab"

Expected Output

"aba"

Input

s = "aaab"

Expected Output

""

Explanation: There are three a's and only one other character, so two a's must end up adjacent.

Hint 1 — click to reveal

It is impossible exactly when some character appears more than (n + 1) / 2 times.

Hint 2 — click to reveal

Always place the character that still has the most remaining — greedily, using a max-heap.

Java Compiler