Untitled
unknown
c_cpp
2 years ago
2.2 kB
5
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<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], sum[i][j]));
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();
}
}Editor is loading...
Leave a Comment