Minimize Ordering

题目描述

给你一个字符串 $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$ 且对于所有整数 $j\ (1 \leq j \lt i)$，有 $s_j=t_j$。 $s_i = t_i$ 对所有整数 $i\ (1 \leq i \leq \min(n,m))$，且 $n \lt m$。

输入格式

输入按照下面的格式由标准输入给出： $S$

输出格式

输出通过重新排列 $S$ 中的字符得到的字典序最小的字符串 $S'$。

aba

aab

zzzz

zzzz

提示

$S$ 是长度在 $1$ 到 $2 \times 10^5$（含）之间的字符串，由小写英文字母组成。通过重新排列 $aba$ 可以得到三种字符串：

$aba$ $aab$ $baa$

其中字典序最小的是 $aab$.

标签: AtCoder|abc242B

来源

AtCoder|abc242B