Description

给出一个字符串 S，你需要从 S 中挑选一对字符进行一次交换（不可以不交换！！！！！！），并让得到的新字符字典序最小！例如：S = "abacc"，如果交换字符 1(a)和 4(c)，得到字符"cbaac"。如果交换字符 2(a)和 3(b)，得到字符"aabcc"。其中："aabcc"的字典序小于"cbaac"。并且"aabcc"是所有交换方法中，字典序最小的。例如：S = "aaab"，则交换 1 和 2，交换 1 和 3，得到的字符都是 "aaab"，并且 "aaab"是所有交换方法中，字典序最小的。输出这个字典序最小的字符。

Input Format

一个字符串 S（S 的只包括 a 到 z 的小写字符，2<=S 的长度<=500000）。

Output Format

字典序最小的新字符串。

abacc

aabcc

Source

CodesOnline