結論として、出力すべき文字列、すなわち \(S\) の各文字を並び替えて得られる文字列 \(S'\) のうち辞書順で最小のものは、\(S\) の各文字を昇順に並び替えて得られる文字列です。

理由を説明します。

\(S\) の各文字を並び替えて得られる文字列 \(S' = S'_1 S'_2 \ldots S'_N\) において、\(S'_i \gt S'_{i+1}\) が成り立つような \(i\ (1 \leq i \leq N-1)\) が存在したとしましょう。するとこのとき、\(S'_i\) と \(S'_{i+1}\) を入れ替えて得られる文字列は \(S'\) よりも辞書順に真に小さいです。

そのため \(S = S_1 S_2 \ldots S_N\) に対して、「\(S_i \gt S_{i+1}\) なる \(i\) について \(S_i\) と \(S_{i+1}\) を入れ替える」という操作を \(S_i \gt S_{i+1}\) なる \(i\) が存在しなくなるまで繰り返すことで辞書順で最小の並び替え \(T\) を得ることができます。

このとき、\(T\) は \(S\) の各文字を昇順で並び替えて得られる文字列に等しいです。

よってこの問題は、「文字列 \(S\) の各文字を昇順に並び替えて出力せよ」という問題に等しいです。

\(S\) を昇順に並び替えること自体は、多くのプログラミング言語において標準ライブラリとして実装されている sort 関数等を用いることで \(O(N \log N)\)で行うことができ、高速です。

実装例 (C++)

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

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

Python を使用する場合、文字列に対して sorted 関数を用いるとそれが list 型に変換されてしまうことに注意してください。

実装例 (Python)

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