分数: 200 点
问题陈述
给你一个字符串 S。找到按字典顺序最小的字符串 S' 通过排列字符获得 S.
这里,对于不同的两个字符串 当满足以下条件之一时, s = s_1 s_2 \ldots s_n 和 t = t_1 t_2 \ldots t_m, s \lt t 按字典顺序成立。
- 有一个整数 i\ (1 \leq i \leq \min(n,m)) 这样 s_i \lt t_i 和 s_j=t_j 对于所有整数 j\ (1 \leq j \lt i).
- s_i = t_i 对于所有整数 i\ (1 \leq i \leq \min(n,m)),和 n \lt m.
约束
- S 是长度介于 1 和 2 \times 10^5 (含)由小写英文字母组成。
输入
输入由标准输入按以下格式给出:
S
输出
打印字典顺序最小的字符串 S' 通过排列字符获得 S.
示例输入 1
aba
示例输出 1
aab
通过排列可以得到三个字符串 aba:
abaaabbaa
其中按字典顺序最小的是 aab.
示例输入 2
zzzz
示例输出 2
zzzz