Contest Duration: - (local time) (100 minutes) Back to Home
Official

## B - Minimize Ordering Editorial by en_translator

In conclusion, the string to be output, that is,the lexicographically smallest string $$S'$$ obtained by permuting the characters of $$S$$, is the string obtained by sorting the characters of $$S$$ in the increasing order.

We will explain the reason.

In a string $$S' = S'_1 S'_2 \ldots S'_N$$ obtained by sorting characters of $$S$$, suppose that there exists $$i\ (1 \leq i \leq N-1)$$ such that $$S'_i \gt S'_{i+1}$$. Then, swapping $$S'_i$$ and $$S'_{i+1}$$ makes the string strictly lexicographically less than $$S'$$.

Therefore, for the string $$S = S_1 S_2 \ldots S_N$$, we can repeat the operation of “swapping $$S_i$$ and $$S_{i+1}$$ for $$i$$ such that $$S_i \gt S_{i+1}$$” until there is no $$i$$ such that $$S_i \gt S_{i+1}$$, so that we obtain the lexicographically smallest permutation $$T$$.

Here, $$T$$ is equal to the string obtained by sorting the characters of $$S$$ in the ascending order.

Hence, the problem is equivalent to the following problem: “sort the characters of $$S$$ in the increasing order and print it.”

Sorting $$S$$ itself can done in a total of $$O(N \log N)$$ time with sort functions that are implemented in many languages as a part of standard library, which is fast enough.

Sample code (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
string S; cin >> S;
sort(S.begin(),S.end());
cout << S << endl;
}


Note that in Python, applying sorted function for a string result in a list type.

Sample code (Python)

s = input()
print(''.join(sorted(s)))


posted:
last update: