Gọi ~S_i~ là ký tự thứ ~i~ từ trái sang của xâu ~S~ ~(1 \le i \le n)~, vậy xâu đối xứng là một xâu thỏa mãn ~S'_i~ = ~S'_{n-i+1}~ ~\forall~ ~(1 \le i \le n)~ và ta cần tìm các điều kiện để tạo được ~S'~ là một xâu đối xứng.

Điều kiện #1~:~ Ta chỉ được phép đổi chỗ các ký tự trong đoạn tiền tố độ dài ~k~ của xâu ~S,~ vậy với mọi chỉ số ~i~ thỏa mãn ~k+1 \le i \le n-k~ thì cả ~S_i~ và ~S_{n-i+1}~ đều không bị ảnh hưởng bởi thao tác đổi chỗ. Nói cách khác~,~ để ~S'~ là xâu đối xứng thì đoạn con ~S_{k+1}, \ldots, S_{n-k}~ phải tạo thành một xâu đối xứng.

Điều kiện #2~:~ Trong trường hợp tồn tại cách xếp thì tiền tố và hậu tố độ dài ~k~ của xâu ~S~ phải là hoán vị của nhau, ta có thể áp dụng nhận xét sau để kiểm tra : cho ~A~ và ~B~ là ~2~ xâu có cùng độ dài~,~ gọi ~A'~ là xâu thu được khi xếp các ký tự trong ~A~ theo thứ tự không giảm và tương tự ta cũng có ~B'~, dễ thấy ~A~ và ~B~ là hoán vị của nhau khi và chỉ khi ~A' = B'~.

Độ phức tạp để kiểm tra ~2~ điều kiện trên là ~O(n)~ hoặc ~O(n*log(n))~ tùy cách cài đặt.

Code mẫu

//TrungNotChung
#include <bits/stdc++.h>
#define pii pair<int , int>
#define fi first
#define se second
#define BIT(x,i) (1&((x)>>(i)))
#define MASK(x)  (1LL<<(x))
#define CNT(x) __builtin_popcountll(x)
#define task "tnc"  

using namespace std;

int cnt[26];
int n, k;
string s;

void solve()
{
    int t; 
    cin >> t;
    while(t--)
    {
        cin >> n >> k >> s;
        memset(cnt, 0 , sizeof(cnt));
        for(int i=0; i<k; ++i) cnt[s[i] - 'a']++;
        for(int i=0; i<k; ++i) cnt[s[n-i-1] - 'a']--;
        bool check = true;
        for(int i=0; i<26; ++i)
        {
            if(cnt[i] != 0) check = false;
        }
        if(!check) cout << "No\n";
        else 
        {
            for(int i=0; i<k; ++i) s[i] = s[n-i-1];
            string t = s;
            reverse(t.begin(), t.end());
            if(s != t) cout << "No\n";
            else 
            {
                cout << "Yes\n";
                cout << s << '\n';
            }
        }

    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);
    #endif // ONLINE_JUDGE
    solve();
    return 0;
}