/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
長さ N の文字列 s が与えられます。 s の i 文字目は s_i と表します。
すぬけ君は以下の手順で s を変化させます。
- (1,2, \ldots, N) の長さが偶数の（連続するとは限らない）部分列 x=(x_1, x_2, \ldots, x_{2k}) を選ぶ(k=0 でも構わない)。
- s_{x_1} と s_{x_{2k}} を入れ替える。
- s_{x_2} と s_{x_{2k-1}} を入れ替える。
- s_{x_3} と s_{x_{2k-2}} を入れ替える。
- \vdots
- s_{x_{k}} と s_{x_{k+1}} を入れ替える。
すぬけ君が手順を終えたあとの s としてありうる文字列のうち、辞書順最小のものを求めてください。
辞書順とは？
辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、相異なる文字列 S と文字列 T の大小を判定するアルゴリズムを以下に説明します。
以下では「 S の i 文字目の文字」を S_i のように表します。また、 S が T より辞書順で小さい場合は S \lt T 、大きい場合は S \gt T と表します。
- S と T のうち長さが短い方の文字列の長さを L とします。i=1,2,\dots,L に対して S_i と T_i が一致するか調べます。
- S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、S_j と T_j を比較して、 S_j がアルファベット順で T_j より小さい場合は S \lt T 、大きい場合は S \gt T と決定して、アルゴリズムを終了します。
- S_i \neq T_i である i が存在しない場合、 S と T の長さを比較して、S が T より短い場合は S \lt T 、長い場合は S \gt T と決定して、アルゴリズムを終了します。
制約
- 1 \leq N \leq 2 \times 10^5
- s は長さ N の英小文字のみからなる文字列
入力
入力は以下の形式で標準入力から与えられる。
N s
出力
すぬけ君が手順を終えたあとの s としてありうる文字列のうち、辞書順最小のものを出力せよ。
入力例 1
4 dcab
出力例 1
acdb
- x=(1,3) のとき、s_{1} と s_{3} のみが入れ替わります。
- 手順を終えたあとの s は
acdbとなり辞書順最小です。
入力例 2
2 ab
出力例 2
ab
- x=() のとき、手順を終えたあとの s は
abとなり辞書順最小です。 - x の長さが 0 でもよいことに注意してください。
入力例 3
16 cabaaabbbabcbaba
出力例 3
aaaaaaabbbbcbbbc
入力例 4
17 snwfpfwipeusiwkzo
出力例 4
effwpnwipsusiwkzo
Score : 400 points
Problem Statement
Given is a string s of length N. Let s_i denote the i-th character of s.
Snuke will transform s by the following procedure.
- Choose an even length (not necessarily contiguous) subsequence x=(x_1, x_2, \ldots, x_{2k}) of (1,2, \ldots, N) (k may be 0).
- Swap s_{x_1} and s_{x_{2k}}.
- Swap s_{x_2} and s_{x_{2k-1}}.
- Swap s_{x_3} and s_{x_{2k-2}}.
- \vdots
- Swap s_{x_{k}} and s_{x_{k+1}}.
Among the strings that s can become after the procedure, find the lexicographically smallest one.
What is the lexicographical order?
Simply speaking, the lexicographical order is the order in which words are listed in a dictionary. As a more formal definition, here is the algorithm to determine the lexicographical order between different strings S and T.
Below, let S_i denote the i-th character of S. Also, if S is lexicographically smaller than T, we will denote that fact as S \lt T; if S is lexicographically larger than T, we will denote that fact as S \gt T.
- Let L be the smaller of the lengths of S and T. For each i=1,2,\dots,L, we check whether S_i and T_i are the same.
- If there is an i such that S_i \neq T_i, let j be the smallest such i. Then, we compare S_j and T_j. If S_j comes earlier than T_j in alphabetical order, we determine that S \lt T and quit; if S_j comes later than T_j, we determine that S \gt T and quit.
- If there is no i such that S_i \neq T_i, we compare the lengths of S and T. If S is shorter than T, we determine that S \lt T and quit; if S is longer than T, we determine that S \gt T and quit.
Constraints
- 1 \leq N \leq 2 \times 10^5
- s is a string of length N consisting of lowercase English letters.
Input
Input is given from Standard Input in the following format:
N s
Output
Print the lexicographically smallest possible string s after the procedure by Snuke.
Sample Input 1
4 dcab
Sample Output 1
acdb
- When x=(1,3), the procedure just swaps s_{1} and s_{3}.
- The s after the procedure is
acdb, the lexicographically smallest possible result.
Sample Input 2
2 ab
Sample Output 2
ab
- When x=(), the s after the procedure is
ab, the lexicographically smallest possible result. - Note that x may have a length of 0.
Sample Input 3
16 cabaaabbbabcbaba
Sample Output 3
aaaaaaabbbbcbbbc
Sample Input 4
17 snwfpfwipeusiwkzo
Sample Output 4
effwpnwipsusiwkzo