Given a string, rearrange its characters so that no two adjacent characters are the same. If multiple valid answers exist, return the lexicographically smallest valid rearrangement. If no valid rearrangement exists, return an empty string.
s = input string
lexicographically smallest valid string with no equal adjacent characters, or empty string if impossible
Example 1:
Input:
s = "aab"
Output:
aba
Explanation:
Only valid rearrangement with no adjacent duplicates is aba.
Example 2:
Input:
s = "aaab"
Output:
Explanation:
Character a appears too many times to avoid adjacent duplicates.