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)))