Given a string s, rearrange the characters so that no two adjacent characters are the same.
Return any valid rearrangement of the string, or return an empty string "" if it is not possible.
Example 1:
Input: s = "aab"
Output: "aba"
Explanation: We can rearrange "aab" into "aba" so that no two adjacent characters are identical.
Example 2:
Input: s = "aaab"
Output: ""
Explanation: It is impossible to rearrange "aaab" so that no two adjacent characters are the same, because the character 'a' appears too many times.
Example 3:
Input: s = "aabb"
Output: "abab"
Explanation: Both "abab" and "baba" are valid answers.
1 <= s.length <= 500s consists of lowercase English letters