Phase Shift (Codeforces 1735C)
Tags: Greedy, dsu

There was a string $$$s$$$ which was supposed to be encrypted. For this reason, all $$$26$$$ lowercase English letters were arranged in a circle in some order, afterwards, each letter in $$$s$$$ was replaced with the one that follows in clockwise order, in that way the string $$$t$$$ was obtained. You are given a string $$$t$$$. Determine the lexicographically smallest string $$$s$$$ that could be a prototype of the given string $$$t$$$.A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ of the same length if and only if:   in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter, that appears earlier in the alphabet than the corresponding letter in $$$b$$$.  

Input: The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 3 \cdot 10^4$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the string $$$t$$$.The next line contains the string $$$t$$$ of the length $$$n$$$, containing lowercase English letters.It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output a single line containing the lexicographically smallest string $$$s$$$ which could be a prototype of $$$t$$$.

Note: In the first test case, we couldn't have the string "a", since the letter a would transit to itself. Lexicographically the second string "b" is suitable as an answer.In the second test case, the string "aa" is not suitable, since a would transit to itself. "ab" is not suitable, since the circle would be closed with $$$2$$$ letters, but it must contain all $$$26$$$. The next string "ac" is suitable.Below you can see the schemes for the first three test cases. The non-involved letters are skipped, they can be arbitrary placed in the gaps.  

Sample Inputs:
5
1
a
2
ba
10
codeforces
26
abcdefghijklmnopqrstuvwxyz
26
abcdefghijklmnopqrstuvwxzy

Sample Outputs:
b
ac
abcdebfadg
bcdefghijklmnopqrstuvwxyza
bcdefghijklmnopqrstuvwxyaz

Solution (Python):
def dfs(parent, child, count):
    if child == None or count >= 26:
        return True
    elif parent == child:
        return False
    else:
        return dfs(parent, encodings.get(child), count + 1)
t = int(input())
for _ in range(t):
    n = int(input())
    t = input()
    encodings = dict()
    s = ''
    rem = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
    for i in range(n):
        if encodings.get(t[i]) != None:
            pass
        else:
            j = 0
            while j < len(rem):
                if dfs(t[i], rem[j], 1):
                    encodings[t[i]] = rem.pop(j)
                    break
                j += 1
        s += encodings.get(t[i], '')
    print(s)

Solution (Python):
import string
for _ in range(int(input())):
    n = int(input())
    st = input()
    s = set()
    mp = {}
    letters = list(string.ascii_lowercase)

    def check(l, c):
        while l in mp:
            l = mp[l]
            if l == c:
                return True
        return False
    for c in st:
        if c in mp:
            continue
        for l in letters:
            if l == c or (l in mp and check(l, c) and (len(mp) < 25)):
                continue
            mp[c] = l
            letters.remove(l)
            break
    print(''.join((mp[c] for c in st)))

Solution (Python):
import sys
input = sys.stdin.readline
t = int(input())

def isgood(alpha, c1, c2):
    c = c2
    r = 0
    while c != 0:
        if c != c1:
            r = r + 1
            c = alpha[c]
        elif r < 25:
            return 0
        else:
            break
    return 1

def convert(s):
    new = ''
    for i in s:
        new += i
    return new
for i in range(t):
    n = int(input())
    c = list(input())
    c = c[:-1]
    alpha = {97: 0}
    for j in range(ord('b'), ord('z') + 1):
        alpha[j] = 0
    r = c
    letters = list(range(97, ord('z') + 1))
    for j in range(n):
        if alpha[ord(r[j])] != 0:
            r[j] = chr(alpha[ord(r[j])])
        else:
            for k in letters:
                if not isgood(alpha, ord(r[j]), k):
                    continue
                alpha[ord(r[j])] = k
                r[j] = chr(k)
                letters.remove(k)
                break
    sys.stdout.write(convert(r) + '\n')