提出 #76079892

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define LONGMAX 1e18
#define INTMAX 2147483647

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

int main()
{
    ll T;
    cin >> T;
    for (ll i = 0; i < T; i++)
    {
        string S;
        cin >> S;
        ll N = S.length();
        vector<ll> cnt(26, 0);
        for (ll j = 0; j < N; j++)
        {
            cnt[S[j] - 'a']++;
        }
        if ((*max_element(cnt.begin(), cnt.end())) > ((N + 1) / 2))
        { // 一番多い文字がM個あったとしたら、M-1個の隙間を埋める必要があり、使える文字はN-M個、つまりN-M<M-1, (N+1)/2<Mで埋められない, このときはNo
            cout << "No" << endl;
            continue;
        }
        priority_queue<pair<ll, char>> pq;
        for (ll j = 0; j < 26; j++)
        {
            if (cnt[j] != 0)
                pq.push({cnt[j], 'a' + j});
        }
        string ans;
        while (pq.size() >= 2) // 2つずつ取り出すので1個以下になったら終了
        {
            auto [c1, ch1] = pq.top();
            pq.pop();
            auto [c2, ch2] = pq.top();
            pq.pop();
            ans += ch1;
            ans += ch2; // 交互に連結させていく
            c1--;       // 在庫が0になるまで
            c2--;
            if (c1 != 0)
                pq.push({c1, ch1});
            if (c2 != 0)
                pq.push({c2, ch2});
        }
        if (!pq.empty()) // 1個残っていたら連結
        {
            ans += pq.top().second;
        }
        cout << "Yes" << endl;
        cout << ans << endl;
    }

    return 0;
}

提出情報

ジャッジ結果