一道很好的构造题，锻炼思维。
以下设原串长为 (len)。
Case 1: 只有一种字符
直接输出原串即可。
Case 2: 有多种字符
Case 2.1: 存在一种字符出现次数为1
显然把这个字符放在最前面，其他字符排序后接在后面即可。
如：( exttt{bbcaaa}) 最优解为 ( exttt{caaabb}) 。
Case 2.2: 所有字符出现次数大于等于2
不妨设最小的字符为 ( exttt{a}) ，其出现次数为 (cnt) 。
那么，最后的答案为 (1) 。
由于要保证字典序最小，我们尽可能多地把 ( exttt{a}) 放在最前。不难发现最前面最多有有连续两个 ( exttt{a}) 。
Case 2.2.1 最前面可以放连续两个a
考虑除这两个 ( exttt{a}) 以外的 ( exttt{a}) ，由于这些 ( exttt{a}) 不能连续出现，所以这些 ( exttt{a}) 每个后要么接一个非 ( exttt{a}) 的字符，要么放在字符串尾。所以，字符串最前面可以放连续两个 ( exttt{a}) ，当且仅当 (cnt-1 le len-cnt+1) （注意：从前往后第二个 ( exttt{a}) 后也要接非 ( exttt{a}) 的字符）。
可行性知道了，那还要构造最优解。显然，我们把所有非 ( exttt{a}) 的字符排序，在相邻两个字符间依次插入 ( exttt{a}) 直至 ( exttt{a}) 用完。如果 ( exttt{a}) 没有用完则一定还剩 (1) 个 ( exttt{a}) ，放在串最后即可。
例：( exttt{baaaaaabcc}) 最优解为 ( exttt{aababacaca})。
Case 2.2.2 最前面不能放连续两个a
那么，最前面只能放一个 ( exttt{a}) 。
在其之后一定会接第二小的字符，不妨设为 ( exttt{b}) 。
那么，后面不能再出现形如 ( exttt{ab}) 这样的串了。
若字符种类 (le 2)，所有的 ( exttt{a}) 应放在所有的 ( exttt{b}) 之后（否则一定会出现形如 ( exttt{ab}) 这样的串）。如 ( exttt{bbabaaaaa}) 的最优解为 ( exttt{abbbaaaaa}) 。
否则，我们可以在最前面的 ( exttt{b}) 后接所有的 ( exttt{a}) ，再接一个第三小的字符（不妨设为 ( exttt{c}) ），然后剩下的字符放置的位置没有限制，直接从小到大排序即可。如 ( exttt{bbaaaaaaaaaccdd}) 的最优解为 ( exttt{abaaaaaaaacbcdd}) 。