Smallest Adjacent-Distinct Arrangement

Given a string s of lowercase English letters, rearrange its characters so that no two adjacent characters are equal.

Among all such rearrangements, return the lexicographically smallest one. If no valid rearrangement exists, return the empty string "".

A rearrangement uses every character of s exactly once.

Examples

Example 1

Input: s = "aab"
Output: "aba"
Explanation: "aba" is the only rearrangement with no equal neighbors.

Example 2

Input: s = "aaab"
Output: ""
Explanation: Three 'a's cannot be separated by a single 'b', so no valid rearrangement exists.

Example 3

Input: s = "aabb"
Output: "abab"
Explanation: "abab" and "baba" both avoid equal neighbors; "abab" is lexicographically smaller.