神秘题目求问

给定长度为 $n$ 的字符串 $s$，求将 $s$ 重排后，可以得到的所有满足每两个相邻字符均不相同的字符串中字典序最小的那一个。

$n \leq 10^6$，所有字符均是小写字母。

样例

In:
ababcc
Out:
abacbc

求原题或解法。