Did We Get Everything Covered? (Codeforces 1925C)
Tags: Greedy, strings

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
input = sys.stdin.readline

def solve():
    (n, k, m) = map(int, input().split())
    s = input().strip()
    ls = 'abcdefghijklmnopqrstuvwxyz'
    st = set()
    ans = ''
    for i in s:
        st.add(i)
        if len(st) == k:
            st = set()
            ans += i
    if len(ans) >= n:
        print('YES')
        return
    print('NO')
    for i in ls:
        if i not in st:
            print(ans + (n - len(ans)) * i)
            break
for _ in range(int(input())):
    solve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
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):
from sys import stdin

def input():
    return stdin.readline()[:-1]

def eureka():
    (n, k, m) = map(int, input().split())
    s = input()
    s1 = 'abcdefghijklmnopqrstuvwxyz'
    s1 = s1[:k]
    l = []
    d1 = {}
    for i in s:
        d1[i] = 1
        if len(d1) == k:
            l.append(i)
            d1 = {}
    if len(l) >= n:
        print('YES')
    else:
        print('NO')
        for i in s1:
            if i not in d1:
                l1 = [i] * (n - len(l))
                break
        l.extend(l1)
        print(''.join(l))
for _ in range(int(input())):
    eureka()