AT_abc242_b [ABC242B] Minimize Ordering

题目描述

给定一个字符串 $S$。请输出通过重新排列 $S$ 的各个字符所能得到的所有字符串 $S'$ 中，字典序最小的那个。

对于两个不同的字符串 $s = s_1 s_2 \ldots s_n$ 和 $t = t_1 t_2 \ldots t_m$，如果它们满足以下任一条件，则认为 $s$ 在字典序上小于 $t$（即 $s < t$）：

• 存在某个整数 $i\ (1 \leq i \leq \min(n, m))$，使得 $s_i < t_i$，且对于所有整数 $j\ (1 \leq j < i)$，都有 $s_j = t_j$。
• 对于所有整数 $i\ (1 \leq i \leq \min(n, m))$，都有 $s_i = t_i$，且 $n < m$。

输入格式

输入从标准输入读取，格式如下：

$S$

输出格式

请输出通过重新排列 $S$ 的各个字符所能得到的所有字符串 $S'$ 中，字典序最小的那个。

输入输出样例 #1

输入 #1

aba

输出 #1

aab

输入输出样例 #2

输入 #2

zzzz

输出 #2

zzzz

说明/提示

限制条件

• $S$ 仅由小写英文字母组成，长度满足 $1 \leq |S| \leq 2 \times 10^5$。

样例解释 1

对于 $S =$ aba，通过重新排列可以得到以下 $3$ 个字符串：

• aba
• aab
• baa 其中字典序最小的是 aab。

由 ChatGPT 4.1 翻译