Untitled

 avatar
unknown
plain_text
a year ago
2.1 kB
3
Indexable
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define PB push_back
#define pii pair<int, int>
using namespace std;
const int N = 2e5 + 5;
const int INF = 1e18;
int a[N], sum[N][30], mp[30], mp2[30];
struct node{
    char a, b;
    int c;
    node(char x, char y, int z) : a(x),b(y),c(z) {}
};
vector<node> fail[30];
void solve(){
    int n, k, m;
    cin >> n >> k >> m;
    string s;
    cin >> s;

    for(int i=0,cnt=0; i<m&&cnt<k; i++){
        if(!mp[s[i]-'a']){
            mp[s[i]-'a'] = 1;
            cnt++;
        }
    }
    // for(int i=0; i<26; i++){
    //     cout << mp[i] << " ";
    // }
    // cout << endl;
    for(int j=0; j<26; j++){
        char ch = 'a' + j;
        // cout << ch << endl;
        for(int i=1; i<=m; i++){
            if(s[i-1] == ch) sum[i][j] = sum[i-1][j] + 1;
            else sum[i][j] = sum[i-1][j];
            // cout << sum[i][j] << " ";
        }
        // cout << endl;
    }

    for(int i=1; i<=m; i++){
        int ii = s[i-1] - 'a';
        if(mp[ii]){
            bool flag = 1;
            for(int j=0; j<26; j++){
                if(mp[j] == 0) continue;
                int target = n - 1;
                if(ii == j) target++;

                if(sum[i][j] < target){
                    flag = 0;
                    fail[ii].PB(node('a'+j, s[i-1], n-1));
                    break;
                }
            }
            if(flag) mp2[ii]++;
        }
    }

    bool win = 1;
    string out = "";
    node nn = node(0, 0, 0);
    for(int i=0; i<26; i++){
        if(mp[i] && !mp2[i]){
            nn = fail[i].back();
            win = 0;
            break;
        }
    }

    if(!win){
        for(int i=0; i<nn.c; i++) out += nn.a;
        out += nn.b;
        cout << "NO" << endl;
        cout << out << endl;
    }
    else cout << "YES" << endl;

    for(int j=0; j<30; j++){
        mp[j] = mp2[j] = 0;
        fail[j].clear();
        for(int i=0; i<=m; i++){
            sum[i][j] = 0;
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int T = 1;
    cin >> T;
    while(T--){
        solve();
    }
}
Leave a Comment