题意:给你一个字符串,要求删去重复的字母,使得只剩下一个字母,那么最后的得到的字符串每个字母都只出现一次,问你怎么操作是的最后的字符串字典序最大.

题解:我们先用后缀和处理每个字母出现的次数,然后再用序列自动机预处理一下,首先我们先得到删去重复字母后字符串的长度,然后再去枚举.

因为要求字典序最大,所以对于每个位置,我们枚举\(['z','a']\),\(cur\)表示当前指针在\(s\)中的所在位置,即\(cur\)之前的元素我们都不要了,如果你了解序列自动机的话,这并不难想.那么对于当前位置\(cur\),我们得到序列自动机\(nx\)数组找到我们当前枚举到的字母的所在位置,因为我们想把我们当前所枚举到的字母放入答案,所以,\([cur,nx[cur][need]-1]\),这段区间的所有字母都需要删去,那么我们怎么知道能不能删呢?这是我们之前处理的后缀和的作用就体现出来了,我们可以枚举\(['a','z']\)每个字母,先看他们在\([cur,nx[cur][need]]\)中是否出现,如果出现,那么在\([nx[cur][need]+1,len(s)]\)这段区间中,它至少要出现一次,那么我们就可以将它删去,这里记个\(flag\)判断一下就好.

代码:

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

int suf[N][26];
int nx[N][26];
int cnt[N],used[N];

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int _;
	cin>>_;
	while(_--){
		string s;
		cin>>s;
		int len=(int)s.size();
		s=" "+s;
		string ans="";

		rep(i,0,25){
			cnt[i]=used[i]=0;
			suf[len+1][i]=0;
			nx[len+1][i]=0;
		}

		per(i,len,1){
			cnt[s[i]-'a']++;
			rep(j,0,25) suf[i][j]=suf[i+1][j];
			suf[i][s[i]-'a']++;
		}
		per(i,len,1){
			rep(j,0,25) nx[i][j]=nx[i+1][j];
			nx[i][s[i]-'a']=i;
		}
		int len_=0;
		rep(i,0,25) len_+=(cnt[i]!=0);

		int cur=1;
		rep(i,1,len_){
			per(need,25,0){
				if(!used[need] && nx[cur][need]){
					int nxt=nx[cur][need];
					int flag=1;
					rep(abd,0,25){
						if(need==abd) continue;
						if(!used[abd] && suf[cur][abd]-suf[nxt+1][abd]){
							flag&=(suf[nxt+1][abd]>0);
						}
					}
					if(flag){
						used[need]=1;
						ans.pb(need+'a');
						cur=nxt+1;
						break;
					}
				}
			}
		}

		cout<<ans<<'\n';

	}

    return 0;
}