点击打开链接
#include <iostream> #include <algorithm> #include <cstdio> #include <cmath> #include <cstring> using namespace std; const int M=1e5+20; char a[M]; int n; int pos[27];//字符出现的最早位置 int main() { int t; cin>>t; while(t--) { char c1,c2; scanf("%s",a); n=strlen(a); memset(pos,0x3f3f3f3f,sizeof(pos)); for(int i=0;i<n;i++) { //操作 //replace all occurrences of the first letter you chose with the second one, //and replace all occurrences of the second letter you chose with the first one. //使得字典序尽量小 //所以从靠前字符开始考虑 与它之后的最小字符互换(最小字符不能出现在它之前) //因为是全部互换 防止互换后变大 :abccac交换后为baccbc显然不符合 pos[a[i]-'a']=min(pos[a[i]-'a'],i);//所以记录字符出现的最早位置 } int flag; for(int i=0;i<n;i++)//复杂度为O(26*n) { flag=0; for(int k=0;k<a[i]-'a';k++)//只由小写字符组成 { if(pos[k]!=0x3f3f3f3f&&pos[k]>pos[a[i]-'a']) { flag=1; c1=a[i]; c2=k+'a'; break; } } if(flag) break; } if(flag) for(int i=0;i<n;i++) { if(a[i]==c1) { a[i]=c2; } else if(a[i]==c2) { a[i]=c1; } } printf("%s\n",a); } return 0; }