题目描述
难度分:1500
输入T(≤105)表示T组数据。所有数据的n之和≤106,m之和≤106。
每组数据输入n(1≤n≤26),k(1≤k≤26),m(1≤m≤1000)和长为m的字符串s,只包含前k个小写字母。
对于所有长为n的只包含前k个小写字母的字符串,是否都是s的子序列?
输出YES
或NO
。
如果输出的是NO
,额外输出任意一个长为n的,只包含前k个小写字母的字符串,其不是s的子序列。
注:子序列不一定连续。
输入样例
3
2 2 4
abba
2 2 3
abb
3 3 10
aabbccabab
输出样例
YES
NO
aa
NO
ccc
算法
构造
如果不输出具体方案,就是个很经典的问题,我们可以准备一个集合。遍历给定的字符串s,每次往集合中放入s[i],如果集合的大小达到了k,说明此时前k个字母都出现过了,就清空集合,继续这个过程。
这个模式如果出现了n次,就能每次从这一个个不相交、且出现过前k个字母的子串中挑一个字母,构成长度为n,且仅由前k个字母组成的任意排列,输出YES
。
否则输出NO
,关键在于怎么构建这个反例。有一种构造方法,前面每次出现集合大小为k时,随便从集合中挑一个字母追加到答案串中。遍历完s后,这个答案串肯定没达到n的长度,遍历字典的前k个字母,用不存在于集合中的字母追加到答案串后面。如果进行完这个操作后长度还不到n,就再补a
补到长度达到n为止。
复杂度分析
时间复杂度
判断是输出YES
还是NO
只需要遍历一遍s串,同时O(1)操作哈希集合,时间复杂度为O(m)。如果输出NO
,构造答案串也是先经历这个过程,时间复杂度为O(m),往后面继续补充字母,直到长度达到n,在最差情况下需要补充O(n)级别的字母,时间复杂度为O(n)。
综上,整个算法的时间复杂度为O(m+n)。
空间复杂度
空间消耗在于哈希集合,额外空间复杂度为O(Σ),其中Σ是字符集大小。但本题字符集仅仅是26个字母,其实可以用一个32位的整数来做状态压缩,这样额外空间就是O(1)了。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int t, n, k, m;
char s[N];
int main() {
scanf("%d", &t);
for(int cases = 1; cases <= t; cases++) {
scanf("%d%d%d", &n, &k, &m);
scanf("%s", s + 1);
bool ok = false;
unordered_set<char> st;
int cnt = 0;
for(int i = 1; i <= m; i++) {
if(s[i] - 'a' < k) {
st.insert(s[i]);
}
if(k == st.size()) {
cnt++;
st.clear();
}
if(cnt == n) {
ok = true;
break;
}
}
if(ok) {
puts("YES");
}else {
puts("NO");
st.clear();
string ans;
for(int i = 1; i <= m; i++) {
if(s[i] - 'a' < k) {
st.insert(s[i]);
}
if(k == st.size()) {
ans.push_back(s[i]);
st.clear();
}
}
for(char c = 'a'; c <= 'a' + k - 1; c++) {
if(!st.count(c) && ans.size() < n) ans.push_back(c);
}
while(ans.size() < n) ans.push_back('a');
cout << ans << endl;
}
}
return 0;
}