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 not possible.

Keeping a map of char frequency. Recursively select chars to construct the answer, return early if one of the solution is found.