Did We Get Everything Covered?（我们是否把所有事情都考虑到了？）

时间限制：2s 内存限制：256MB

【原题地址】

点击此处跳转至原题

【问题描述】

给你两个整数 n 和 k 以及一个字符串 s 。

您的任务是检查是否所有长度为 n 的字符串都可以用前 k 个小写英文字母组成，并作为 s 的子序列出现。如果答案是否定的，那么您还需要打印一个长度为 n 的字符串，该字符串可以用第一个 k 小写英文字母组成，但不会作为 s 的子序列出现。

如果有多个答案，您可以打印任意一个。

注： 如果从 b 中删除一些字符(可能为零)而不改变其余字符的顺序，就可以得到 a ，那么字符串 a 就被称为另一个字符串 b 的子串。

【输入格式】

第一行输入包含一个整数 t(1≤t≤10^5) ，即测试用例的数量。

每个测试用例的第一行包含 3 个整数 n(1≤n≤26),k(1≤k≤26),m(1≤m≤1000) ，其中 n 和 k 与输入中的描述相同， m 是字符串 s 的长度。

每个测试用例的第二行包含一个长度为 m 的字符串 s ，其中只有前 k 个小写英文字母。

保证所有测试用例的 m 和 n 之和不超过 10^6 。

【输出格式】

对于每个测试用例，如果用前 k 个小写英文字母组成的长度为 n 的所有可能字符串都出现在 s 的子序列中，则打印 “是”，否则打印 “否”。

如果答案为 “否”，请在下一行中打印一个长度为 n 的字符串，该字符串可以用前 k 个小写英文字母组成，但不会作为 s 的子序列出现。

您可以在任何情况下打印 YES 或 NO 的每个字母(例如，YES、yES、YeS 都将被视为肯定答案)。

【样例输入】

32 2 4abba2 2 3abb3 3 10aabbccabab

【样例输出】

YESNOaaNOccc

【样例说明】

对于第一个测试用例，所有可能的长度为 2 的字符串(aa、ab、ba、bb)，只要能用前 2 个英文字母组成，都会作为 abba 的子序列出现。长度为 2 的所有可能字符串(aa、ab、ba、bb)。

对于第二个测试用例，字符串 aa 不是 abb 的子序列。

【解题思路】

老汉使用到的是贪心的解题方式

本题是求字符串 s 是否满足。用前 k 个小写英文字母组成的长度为 n 的所有可能字符串都为 s 的子序列。
我们只需贪婪的去求一个用前 k 个小写英文字母组成的长度为 n 的字符串 strb ， strb 贪婪地做到需要 n 组完整且无序的 ‘a’ ~ ‘a’+k-1 序列，如果 s 足够凑出 strb 则答案为 YES ，否则为 NO 。

代码注释有详细过程

【代码】

package CF1925_C_DidWeGetEverythingCovered;import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);// 接收题目数据tint t = scan.nextInt();// 一共t组数据，分别计算输出结果while (t-- > 0) {// 接收数据nint n = scan.nextInt();// 接收数据kint k = scan.nextInt();// 接收数据mint m = scan.nextInt();// 接收数据sString str = scan.next();// 创建字符串strb，用于存放长度为n，是极其难构成的，每个字符都需要一组完整且无序的a~a+k-1的序列构成。// 当strb能被s构成，即长度等于n时，答案为YES，否则，即长度小于n时，答案为NOStringBuffer strb = new StringBuffer();// 布尔数组used，表示当前下标对应的字符是否被使用，默认为false（未使用）boolean[] used = new boolean[k];// 用于判断是否足够凑出strb的一个字符序列int count = 0;// 遍历str字符串中的每个字符for (char c : str.toCharArray()) {// 当strb能被s构成时，退出循环，输出答案YESif (strb.length() == n) {break;}// 当前字符未被使用过，对count进行加1，标记当前字符为已使用if (!used[c - 'a']) {count++;used[c - 'a'] = true;}// 当使用过的字符数足够凑出一个strb字符时，对count、used设置回初始状态，将当前字符添加进strbif (count == k) {count = 0;used = new boolean[k];strb.append(c);}}// 当strb能被s构成时，输出答案YES，否则输出答案NO以及strbif (strb.length() == n) {System.out.println("YES");} else {System.out.println("NO");// 遍历a~a+k-1，对strb进行补齐for (int i = 0; i < k; i++) {// 当对应字符未被使用时，即代表最后一组凑出strb字符的序列组至str末尾都未出现过，使用该字符对strb补齐为止if (!used[i]) {while (strb.length() < n) {strb.append((char) ('a' + i));}// 补齐后退出循环break;}}// 输出结果strbSystem.out.println(strb.toString());}}scan.close();}}