Given a string s of lowercase letters, rearrange the characters so that no two adjacent characters are equal. Return any valid rearrangement, or an empty string if no rearrangement is possible.
Input
s: a string of lowercase letters
Output
A rearranged string with no two adjacent characters equal, or "" if impossible.
Examples
Example 1
Inputs = "aab"
Outputaba
Example 2
Inputs = "aaab"
Output(empty string)
Explanation: One letter appears more than ceil(n/2) times, so no valid arrangement exists.
Constraints
1 <= s.length <= 500
Greedy approach: repeatedly take the most frequent remaining letter that differs from the previous placement.