Unstable String Sort (Codeforces 1213F)
Tags: Greedy, dsu

Authors have come up with the string $$$s$$$ consisting of $$$n$$$ lowercase Latin letters.You are given two permutations of its indices (not necessary equal) $$$p$$$ and $$$q$$$ (both of length $$$n$$$). Recall that the permutation is the array of length $$$n$$$ which contains each integer from $$$1$$$ to $$$n$$$ exactly once.For all $$$i$$$ from $$$1$$$ to $$$n-1$$$ the following properties hold: $$$s[p_i] \le s[p_{i + 1}]$$$ and $$$s[q_i] \le s[q_{i + 1}]$$$. It means that if you will write down all characters of $$$s$$$ in order of permutation indices, the resulting string will be sorted in the non-decreasing order.Your task is to restore any such string $$$s$$$ of length $$$n$$$ consisting of at least $$$k$$$ distinct lowercase Latin letters which suits the given permutations.If there are multiple answers, you can print any of them.

Input: The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5, 1 \le k \le 26$$$) — the length of the string and the number of distinct characters required.The second line of the input contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$, all $$$p_i$$$ are distinct integers from $$$1$$$ to $$$n$$$) — the permutation $$$p$$$.The third line of the input contains $$$n$$$ integers $$$q_1, q_2, \dots, q_n$$$ ($$$1 \le q_i \le n$$$, all $$$q_i$$$ are distinct integers from $$$1$$$ to $$$n$$$) — the permutation $$$q$$$.

Output: If it is impossible to find the suitable string, print "NO" on the first line.Otherwise print "YES" on the first line and string $$$s$$$ on the second line. It should consist of $$$n$$$ lowercase Latin letters, contain at least $$$k$$$ distinct characters and suit the given permutations.If there are multiple answers, you can print any of them.


Sample Inputs:
3 2
1 2 3
1 3 2

Sample Outputs:
YES
abb

Solution (Python):
def main():
    (n, m) = map(int, input().split())
    abc = list('zyxwvutsrqponmlkjihgfedcba'[26 - m:])
    res = [abc[0]] * (n + 1)
    (res[0], pool, f) = ('YES\n', [False] * (n + 1), 0)
    for (p, q) in zip(map(int, input().split()), map(int, input().split())):
        if pool[p]:
            f -= 1
        else:
            pool[p] = True
            f += 1
        if pool[q]:
            f -= 1
        else:
            pool[q] = True
            f += 1
        res[p] = abc[-1]
        if not f:
            del abc[-1]
            if not abc:
                break
    print('NO' if abc else ''.join(res))
if __name__ == '__main__':
    main()

Solution (Python):
import sys

def main():
    (n, m) = [int(x) for x in sys.stdin.readline().strip().split()]
    p = [int(x) for x in sys.stdin.readline().strip().split()]
    q = [int(x) for x in sys.stdin.readline().strip().split()]
    sp = set()
    hashp = 0
    sq = set()
    hashq = 0
    res = ['z' for _ in range(n)]
    x = 0
    for (c1, c2) in zip(p, q):
        sp.add(c1)
        hashp += c1 * c1
        sq.add(c2)
        hashq += c2 * c2
        if hashp == hashq and sp == sq:
            c = chr(ord('a') + x)
            x += 1
            for pos in sp:
                res[pos - 1] = c
            if x == m:
                print('YES')
                print(''.join(res))
                return
            sp.clear()
            hashp = 0
            sq.clear()
            hashq = 0
    print('NO')
main()

Solution (Python):
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
s = list(map(int, input().split()))
d = [0] * (n + 5)
for q in range(n):
    d[s[q]] = q
(f, q2) = ([], 0)
for q in range(len(a)):
    if q - 1 == q2:
        f.append(q)
    q2 = max(q2, d[a[q]])
f.append(n)
if len(f) < k:
    print('NO')
else:
    print('YES')
    g = [chr(ord('a') + q) for q in range(30)]
    ans = ['' for q in range(n)]
    q1 = 0
    for q in range(n):
        if f[q1] == q:
            q1 += 1
            q1 = min(q1, 25)
        ans[a[q] - 1] = g[q1]
    print(''.join(ans))