Description
Given a string s, rearrange the characters so that no two adjacent characters are the same. Return any valid rearrangement, or return an empty string if not possible.
Examples
Input:
s = "aab"Output:
"aba"Explanation:
Rearranged so no two adjacent chars are same.
Input:
s = "aaab"Output:
""Explanation:
Not possible to rearrange without adjacent same chars.
Input:
s = "aabbcc"Output:
"ababcb"Explanation:
With multiple characters having equal frequency, it is possible to alternate between them. Starting with 'a', then 'b', then 'c', and continuing this pattern ensures no two adjacent characters are the same.
Constraints
- •
1 ≤ s.length ≤ 500 - •
s consists of lowercase English letters.