Submission #76053271

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define inf 4e18
#define eps 1e-9
#define il inline
#define ls 2*k
#define rs 2*k+1
using namespace std;
const int N=3e5+5,M=250005;
const int mod=998244353;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n,cnt[30];
string s;
priority_queue< pair<int,int> >q;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int tc;cin>>tc;
	while(tc--){
		cin>>s;
		n=s.size();
		s=" "+s;
		int maxn=0;
		for(int i=1;i<=n;i++){
			int now=s[i]-'a'+1;
			cnt[now]++;
			maxn=max(maxn,cnt[now]);
		}
		if(maxn>(n+1)/2){
			cout<<"No\n";
			for(int i=1;i<=26;i++) cnt[i]=0;
			continue;
		}
		cout<<"Yes\n";
		while(!q.empty()) q.pop();
		for(int i=1;i<=26;i++)
			q.push({cnt[i],i});
		int pre=-1;
		for(int i=1;i<=n;i++){
			auto tmp=q.top();
			q.pop();
			if(tmp.second==pre){
				auto now=q.top();
				q.pop();
				q.push(tmp);
				pre=now.second;
				if(now.first-1>=1)
					q.push({now.first-1,now.second});
			}
			else{
				pre=tmp.second;
				if(tmp.first-1>=1)
					q.push({tmp.first-1,tmp.second});
			}
			char ch=('a'+pre-1);
			cout<<ch;
		}
		cout<<'\n';
		for(int i=1;i<=26;i++) cnt[i]=0;
		while(!q.empty()) q.pop();
	}
	return 0;
}
/*
input： 
1
3 4 1
1 2 3
3 3 4 7 
6
output：
14

从大到小按位考虑，则如果能在不会让前面取不到的情况下取到，那么一定要操作。 
*/

Submission Info

Judge Result