1924A.md (2309B)
1 Source: https://codeforces.com/problemset/problem/1924/A 2 3 A. Did We Get Everything Covered? 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given two integers $n$ and $k$ along with a string $s$. 22 23 Your task is to check whether all possible strings of length $n$ that can be formed using the first $k$ lowercase English alphabets occur as a subsequence of $s$. If the answer is NO, you also need to print a string of length $n$ that can be formed using the first $k$ lowercase English alphabets which does not occur as a subsequence of $s$. 24 25 If there are multiple answers, you may print any of them. 26 27 Note: A string $a$ is called a subsequence of another string $b$ if $a$ can be obtained by deleting some (possibly zero) characters from $b$ without changing the order of the remaining characters. 28 29 Input 30 31 The first line of input contains a single integer $t \, (1 \le t \le 10^5)$, the number of test cases. 32 33 The first line of each test case contains $3$ integers $n \, (1 \le n \le 26), \: k \, (1 \le k \le 26), \: m \, (1 \le m \le 1000)$, where $n$ and $k$ are the same as described in the input and $m$ is the length of the string $s$. 34 35 The second line of each test case contains a single string $s$ of length $m$, comprising only of the first $k$ lowercase English alphabets. 36 37 It is guaranteed that the sum of $m$ and the sum of $n$ over all test cases does not exceed $10^6$. 38 39 Output 40 41 For each test case, print YES if all possible strings of length $n$ that can be formed using the first $k$ lowercase English alphabets occur as a subsequence of $s$, else print NO. 42 43 If your answer is NO, print a string of length $n$ that can be formed using the first $k$ lowercase English alphabets which does not occur as a subsequence of $s$ in the next line. 44 45 You may print each letter of YES or NO in any case (for example, YES, yES, YeS will all be recognized as a positive answer). 46 47 Example 48 49 Input 50 51 ``` 52 3 53 54 2 2 4 55 56 abba 57 58 2 2 3 59 60 abb 61 62 3 3 10 63 64 aabbccabab 65 ``` 66 67 Output 68 69 ``` 70 YES 71 NO 72 aa 73 NO 74 ccc 75 ``` 76 77 Note 78 79 For the first test case, all possible strings (aa, ab, ba, bb) of length $2$ that can be formed using the first $2$ English alphabets occur as a subsequence of abba. 80 81 For the second test case, the string aa is not a subsequence of abb.