题目描述

难度分:$1500$

输入$T(\leq 10^5)$表示$T$组数据。所有数据的$n$之和$\leq 10^6$，$m$之和$\leq 10^6$。

每组数据输入$n(1 \leq n \leq 26)$，$k(1 \leq k \leq 26)$，$m(1 \leq m \leq 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(\Sigma)$，其中$\Sigma$是字符集大小。但本题字符集仅仅是$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;
}