C. Equal Frequencies

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
const int N=1e6+10,INF=0x3f3f3f3f;

int n;
string s;
int cnt[26];
PII g[26];

bool cmp(PII a,PII b)
{
    return a.first>b.first;
}

void solve()
{
    cin>>n>>s;

    memset(cnt,0,sizeof cnt);

    for(int i=0;i<n;i++)    //统计字符串中每种字符出现的次数
        cnt[s[i]-'a']++;

    for(int i=0;i<26;i++)   //暴力枚举26个字符
        g[i]={cnt[i],i};

    sort(g,g+26,cmp);   //将26个字符按照出现次数从大到小排序

    //  贪心的思想，保留前i种出现次数最多的字符

    int ans=INF,num=0;  //ans表示最小操作次数,num表示前几种字符

    for(int i=1;i<=26;i++)  //枚举保留前几种字符
    {
        if(n%i==0)  //根据题意知，字符种类*K==n
        {
            int t=0,sum=n/i;    //sum表示每种字符需要有多少个
            for(int j=0;j<i;j++)
                t+=abs(sum-cnt[g[j].second]);   //前i种字符，如果大于sum就删除，小于sum就添加
            for(int j=i;j<26;j++)
                t+=cnt[g[j].second];    //剩下的字符全部删除
            if(ans>t/2) ans=t/2,num=i;  //因为一个操作可以达到删除和添加两种结果，所有t/2代表操作次数
        }
    }

    for(int i=0;i<num;i++)  //前num种字符保留，每种字符有n/num个
        cnt[g[i].second]-=n/num;

    for(int i=0,j=num-1;i<n;i++)    //i:0~n-1,从0~n-1枚举s中的每个字符
    {
        while(j>=0&&cnt[g[j].second]>=0)    j--;//j用来枚举前num种字符中小于0的

        if(cnt[s[i]-'a']>0)
        {
            cnt[s[i]-'a']--;
            cnt[g[j].second]++;
            s[i]='a'+g[j].second;
        }

    }

    cout<<ans<<endl<<s<<endl;
}

int main()
{
    int T;

    T=1;

    cin>>T;

    while(T--)  solve();

    return 0;
}