Untitled
#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<n; 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