Did We Get Everything Covered? (Codeforces 1924A)
Tags: Greedy, shortest paths

You are given two integers $$$n$$$ and $$$k$$$ along with a string $$$s$$$.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$$$.If there are multiple answers, you may print any of them.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.

Input: The first line of input contains a single integer $$$t \, (1 \le t \le 10^5)$$$, the number of test cases.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$$$.The second line of each test case contains a single string $$$s$$$ of length $$$m$$$, comprising only of the first $$$k$$$ lowercase English alphabets.It is guaranteed that the sum of $$$m$$$ and the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output: 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.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.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).

Note: 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.For the second test case, the string aa is not a subsequence of abb.

Sample Inputs:
3
2 2 4
abba
2 2 3
abb
3 3 10
aabbccabab

Sample Outputs:
YES
NO
aa
NO
ccc

Solution (Python):
import sys
MOD = 1000000007
input = sys.stdin.readline
alpha = 'abcdefghijklmnopqrstuvwxyz'

def solve():
    (n, k, m) = map(int, input().split())
    s = input().strip()
    d = set()
    ans = ''
    for i in range(m):
        d.add(s[i])
        if len(d) == k:
            d.clear()
            ans += s[i]
    if len(ans) >= n:
        print('YES')
    else:
        print('NO')
        for i in alpha:
            if i not in d:
                while len(ans) < n:
                    ans += i
                break
        print(ans)
t = int(input())
for _ in range(t):
    solve()

Solution (Python):
import sys

def run():
    (n, k, m) = [int(x) for x in sys.stdin.readline().split()]
    s = sys.stdin.readline().strip()
    seen = set()
    lastChars = ''
    for c in s:
        if c not in seen:
            seen.add(c)
            if len(seen) == k:
                lastChars += c
                seen.clear()
    if len(lastChars) >= n:
        print('YES')
    else:
        print('NO')
        for j in range(k):
            c = chr(ord('a') + j)
            if c not in seen:
                lastChars += c
                break
        while len(lastChars) < n:
            lastChars += 'a'
        print(lastChars)
if __name__ == '__main__':
    t = int(sys.stdin.readline().strip())
    for _ in range(t):
        run()

Solution (Python):
import sys

def run():
    (n, k, m) = [int(x) for x in sys.stdin.readline().split()]
    s = sys.stdin.readline().strip()
    seen = set()
    i = 0
    lastChars = ''
    while i < len(s):
        if s[i] not in seen:
            seen.add(s[i])
            if len(seen) == k:
                lastChars += s[i]
                seen.clear()
        i += 1
    if len(lastChars) >= n:
        print('YES')
    else:
        print('NO')
        for j in range(k):
            c = chr(ord('a') + j)
            if c not in seen:
                lastChars += c
                break
        while len(lastChars) < n:
            lastChars += 'a'
        print(lastChars)
if __name__ == '__main__':
    t = int(sys.stdin.readline().strip())
    for _ in range(t):
        run()