1781C - Equal Frequencies - CodeForces Solution

/*************************************************************************************************************
                                        ⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⠛⠛⠛⠋⠉⠈⠉⠉⠉⠉⠛⠻⢿⣿⣿⣿⣿⣿⣿⣿
                                        ⣿⣿⣿⣿⣿⡿⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠛⢿⣿⣿⣿⣿
                                        ⣿⣿⣿⣿⡏⣀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣤⣤⣄⡀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣿⣿
                                        ⣿⣿⣿⢏⣴⣿⣷⠀⠀⠀⠀⠀⢾⣿⣿⣿⣿⣿⣿⡆⠀⠀⠀⠀⠀⠀⠀⠈⣿⣿
                                        ⣿⣿⣟⣾⣿⡟⠁⠀⠀⠀⠀⠀⢀⣾⣿⣿⣿⣿⣿⣷⢢⠀⠀⠀⠀⠀⠀⠀⢸⣿
                                        ⣿⣿⣿⣿⣟⠀⡴⠄⠀⠀⠀⠀⠀⠀⠙⠻⣿⣿⣿⣿⣷⣄⠀⠀⠀⠀⠀⠀⠀⣿
                                        ⣿⣿⣿⠟⠻⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠶⢴⣿⣿⣿⣿⣿⣧⠀⠀⠀⠀⠀⠀⣿
                                        ⣿⣁⡀⠀⠀⢰⢠⣦⠀⠀⠀⠀⠀⠀⠀⠀⢀⣼⣿⣿⣿⣿⣿⡄⠀⣴⣶⣿⡄⣿
                                        ⣿⡋⠀⠀⠀⠎⢸⣿⡆⠀⠀⠀⠀⠀⠀⣴⣿⣿⣿⣿⣿⣿⣿⠗⢘⣿⣟⠛⠿⣼
                                        ⣿⣿⠋⢀⡌⢰⣿⡿⢿⡀⠀⠀⠀⠀⠀⠙⠿⣿⣿⣿⣿⣿⡇⠀⢸⣿⣿⣧⢀⣼
                                        ⣿⣿⣷⢻⠄⠘⠛⠋⠛⠃⠀⠀⠀⠀⠀⢿⣧⠈⠉⠙⠛⠋⠀⠀⠀⣿⣿⣿⣿⣿
                                        ⣿⣿⣧⠀⠈⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠟⠀⠀⠀⠀⢀⢃⠀⠀⢸⣿⣿⣿⣿
                                        ⣿⣿⡿⠀⠴⢗⣠⣤⣴⡶⠶⠖⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⡸⠀⣿⣿⣿⣿
                                        ⣿⣿⣿⡀⢠⣾⣿⠏⠀⠠⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠛⠉⠀⣿⣿⣿⣿
                                        ⣿⣿⣿⣧⠈⢹⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⣿⣿⣿⣿
                                        ⣿⣿⣿⣿⡄⠈⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⣴⣾⣿⣿⣿⣿⣿
                                        ⣿⣿⣿⣿⣧⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿
                                        ⣿⣿⣿⣿⣷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
                                        ⣿⣿⣿⣿⣿⣦⣄⣀⣀⣀⣀⠀⠀⠀⠀⠘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
                                        ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⡄⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
                                        ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⠀⠀⠀⠙⣿⣿⡟⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿
                                        ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⠀⠁⠀⠀⠹⣿⠃⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿
                                        ⣿⣿⣿⣿⣿⣿⣿⣿⡿⠛⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⢐⣿⣿⣿⣿⣿⣿⣿⣿⣿
                                        ⣿⣿⣿⣿⠿⠛⠉⠉⠁⠀⢻⣿⡇⠀⠀⠀⠀⠀⠀⢀⠈⣿⣿⡿⠉⠛⠛⠛⠉⠉
                                        ⣿⡿⠋⠁⠀⠀⢀⣀⣠⡴⣸⣿⣇⡄⠀⠀⠀⠀⢀⡿⠄⠙⠛⠀⣀⣠⣤⣤⠄
*************************************************************************************************************/
#include<bits/stdc++.h>
using namespace std;

typedef long long  ll;
typedef long double ld;

#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define vi vector<int>
#define vll vector<ll>
#define ump unordered_map
#define lp(i,a,b) for(ll i = a ; i<b ; i++)
#define lpp(i,a,b) for(int i = a ; i >= b ; i--)
#define llp(x , a) for(auto x : a)
#define pb push_back
#define pf push_front
#define popf pop_front
#define popb pop_back
#define all(x) x.begin(),x.end()
#define YES cout<<"YES"<<"\n";
#define NO cout<<"NO"<<"\n";
#define mod 10000000+7
#define INF 1e18

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x);
#else
#define debug(x)
#endif

template<class T> void _print(vector<T> arr){
    cerr<<"[ ";
    for(auto x : arr){
        cerr<<x<<" ";
    }
    cerr<<"]";
    cerr<<"\n";
}

template<class T , class V> void _print(map<T , V> mp){
    cerr<<"{ \n";
    for(auto x : mp){
        cerr<<"\t"<<x.first<<" : "<<x.second<<"\n";
    }
    cerr<<"}";
    cerr<<"\n";
}

template<class T , class V> void _print(unordered_map<T , V> mp){
    cerr<<"{ \n";
    for(auto x : mp){
        cerr<<"\t"<<x.first<<" : "<<x.second<<"\n";
    }
    cerr<<"}";
    cerr<<"\n";
}

template<class T , class V> void _print(pair<T , V> p){
    cerr<<"{ "<<p.first<<" "<<p.second<<" }"<<"\n";
}

template<class T> void _print(T x){
    cerr<<x<<"\n";
}

void solve()
{
    // main code
    ll n;
    cin >> n;
    string s;
    cin >> s;
    map<char, ll> m;
    priority_queue<ll> pq, pq2;
    vector<ll> v(26, 0);
    for(int i=0; i<n; i++){
        m[s[i]]++;
        v[s[i] - 'a']++;
    }

    for(auto it : m){
        pq.push(it.second);
    }
    pq2 = pq;

    // our task would be to eliminate the alphabets with the lowest frequency;

    ll ANS = n;
    ll idx = 1;
    for(int i=1; i<=min(n, 26ll); i++){
        // i is the amount of unique characters i would have
        if(n % i == 0){
            // proceed
            pq = pq2;
            ll ans = 0;
            ll needed = n / i;
            ll extra = 0;
            ll count = 0;
            while(count < i){

                if(pq.empty()){
                    break;
                }

                ll curr = pq.top();
                // debug(pq.top())
                pq.pop();

                if(curr < needed){
                    if(extra >= needed - curr){
                        extra -= needed - curr;
                    }
                    else{
                        ans += needed - curr - extra;
                        extra = 0;
                    }
                }
                else{
                    extra += curr - needed;
                    ans += curr - needed;
                }

                count++;
            }
            // cerr << "i = " << i << " : " << "ans = " << ans << endl;
            if(ans < ANS){
                ANS = ans;
                idx = i;
            }
        }
    }
    cerr << "idx = " << idx << " : " << "ANS = " << ANS << endl;
    cerr << endl;
    cout << ANS << endl;

    // we need idx amount of unique characters;

    // our map contains all the values of the alphabets;

    // if(unique characters already >= idx) change / delete the existing ones;
    // else create new ones

    pq = pq2;
    priority_queue<pair<ll, char>> pqq;
    for(auto it : m){
        pqq.push({it.second, it.first});
    }
    vector<bool> used(26, false);
    ll temp = idx;
    while(1){
        if(temp == 0 || pqq.empty()) break;
        temp--;
        char c = pqq.top().second;
        pqq.pop();
        used[c - 'a'] = true;
    }
    for(int i=0; i<26; i++){
        debug(i)
        if(temp){
            debug(i)
            if(!used[i]){
                used[i] = true;
                temp--;
            }
        }
        else break;
    }
    debug(used)

    // now used contains all the characters needed to be added

    // vector v contains the amount of characters i have of each particular alphabet

    // all of them need to be n / idx;

    priority_queue<pair<ll, char>> need;

    for(int i=0; i<26; i++){
        if(used[i] && v[i] < n / idx){
            need.push({n / idx - v[i], 'a' + i});
        }   
    }
    vector<ll> newcounter(26, 0);
    for(int i=0; i<n; i++){
        debug(s[i])
        if(used[s[i] - 'a'] == true){
            debug(1)
            if(newcounter[s[i] - 'a'] < n / idx){
                debug(2)
                newcounter[s[i] - 'a']++;
            }
            else{
                debug(3)
                pair<ll, char> p = need.top();
                need.pop();
                s[i] = p.second;
                newcounter[s[i] - 'a']++;
                if(p.first - 1 > 0) need.push({p.first - 1, p.second});
            }
        }
        else{
            pair<ll, char> p = need.top();
            need.pop();
            s[i] = p.second;
            newcounter[s[i] - 'a']++;
            if(p.first - 1 > 0) need.push({p.first - 1, p.second});
        }
    }
    cout << s << endl;


    return ;
}

int main()
{

#ifndef ONLINE_JUDGE
    freopen("Error.txt", "w", stderr);
#endif

    fastio();

    int t;
    cin>>t; 
    while(t--)
    {
        solve();
    }

    return 0;
    
}