Given a string s, rearrange its characters so that no two adjacent characters are the same. Return any such rearrangement, or the empty string "" if none exists.
Because several arrangements can be valid, your answer is checked for the rules rather than compared to a fixed string: it must use exactly the characters of s, and no two neighbours may be equal.
Examples
Input: s = "aab"
Output: "aba"
Input: s = "aaab"
Output: ""
Explanation: three a's cannot be separated by a single b.
Input: s = "vvvlo"
Output: "vlvov"
Explanation: "vovlv" would also be accepted.
Constraints
0 <= len(s) <= 10**5, lowercase letters only- Target complexity: O(n log a) where
ais the alphabet size.
Goals
- Detect when a rearrangement is impossible from the character counts
- Always place the most frequent remaining character that is not the previous one
- Hold back the just-used character for one round