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:
Character 'a' appears 3 times in a 4-character string. Since 'a' count exceeds (length+1)/2 = 2, it's impossible to place 'a's without two being adjacent.
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.