o(n)做法tle了求助,贪心+构造

using namespace std;
int lj[27],a,b,c,type,T;
string st;
inline void pc(int i)
{
	--lj[i];
	putchar('a'+i-1);
} 
int main()
{
	cin>>T;
	while(T--)
	{
		memset(lj,0,sizeof(lj));
		cin>>st;
		type=a=b=0;
		for(int i=0;i<st.size();i++) ++lj[st[i]-'a'+1];
		for(int i=1;i<=26;i++)
		{
			if(lj[i]==1) {pc(i);type=1;break;} else
				if(!type&&lj[i]==st.size()) {type=2;break;}
			if(!a&&lj[i]<=st.size()/2+1) type=3;
			if(!c&&a&&b&&lj[i]) c=i;
			if(a&&!b&&lj[i]) b=i;
			if(!a&&lj[i]) a=i;
		}
		if(type==1)
			for(int i=1;i<=26;i++)
				while(lj[i]) pc(i);
		if(type==2) cout<<st;
		if(type==3)
		{
			pc(a),pc(a);
			while(lj[a])
			{
				while(!lj[b]) b++;
				pc(b);
				pc(a);
			} 
			for(int i=1;i<=26;i++)
				while(lj[i]) pc(i);
		}
		if(!type)
		{
			pc(a);
			pc(b);
			if(!c)
			{
				while(lj[b]) pc(b);
				while(lj[a]) pc(a);
			}else
			{
				while(lj[a]) pc(a);
				pc(c);
				for(int i=1;i<=26;i++)
					while(lj[i]) pc(i);
			}
		} 
		cout<<endl;
	}
	return 0;
}