← 返回题目列表

AtCoder · abc242_b

D. 最小化订购

中文机器翻译题面 查看原题

分数: 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:

  • aba
  • aab
  • baa

其中按字典顺序最小的是 aab.


示例输入 2

zzzz

示例输出 2

zzzz