B - Minimize Ordering Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

文字列 S が与えられます。S の各文字を並び替えて得られる文字列 S' のうち、辞書順で最小のものを出力してください。

なお、相異なる 2 つの文字列 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
  • すべての整数 i\ (1 \leq i \leq \min(n,m)) について s_i = t_i かつ、n \lt m

制約

  • S は英小文字のみからなる長さ 1 以上 2 \times 10^5 以下の文字列

入力

入力は以下の形式で標準入力から与えられる。

S

出力

S の各文字を並び替えて得られる文字列 S' のうち、辞書順で最小のものを出力せよ。

入力例 1

aba

出力例 1

aab

S= aba を並び替えて得られる文字列は以下の 3 つが考えられます。

  • aba
  • aab
  • baa

この中で辞書順で最小のものは、aab です。

入力例 2

zzzz

出力例 2

zzzz

Score : 200 points

Problem Statement

You are given a string S. Find the lexicographically smallest string S' obtained by permuting the characters of S.

Here, for different two strings s = s_1 s_2 \ldots s_n and t = t_1 t_2 \ldots t_m, s \lt t holds lexicographically when one of the conditions below is satisfied.

  • There is an integer i\ (1 \leq i \leq \min(n,m)) such that s_i \lt t_i and s_j=t_j for all integers j\ (1 \leq j \lt i).
  • s_i = t_i for all integers i\ (1 \leq i \leq \min(n,m)), and n \lt m.

Constraints

  • S is a string of length between 1 and 2 \times 10^5 (inclusive) consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

S

Output

Print the lexicographically smallest string S' obtained by permuting the characters in S.

Sample Input 1

aba

Sample Output 1

aab

Three strings can be obtained by permuting aba:

  • aba
  • aab
  • baa

The lexicographically smallest among them is aab.

Sample Input 2

zzzz

Sample Output 2

zzzz