貪欲法.
- アルファベット順の小さいほうから試す
- 右側から優先して選ぶ
- 左側からも優先して選ぶ
左,右から選ぶindexを\(l, r\) とすると, 常に \(l \leq r \) である. このことに注意すると, \(O(N)\) で実装できる.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main(){
int n;
string s;
cin>>n>>s;
int a,b;
a = 0;
b = n-1;
for(int i='a'; i<='z';i++)
{
int l = a;
dsrep(r, b+1, l+1) if(s[r]==i){
while(s[l]<=i && l<r)
l++;
if(s[l] > s[r]){
swap(s[l],s[r]);
a = ++l;
b = r-1;
}
}
}
cout<<s<<"\n";
}