Perfect Keyboard (Codeforces 1303C)
Tags: Greedy, dfs and similar

Polycarp wants to assemble his own keyboard. Layouts with multiple rows are too complicated for him — his keyboard will consist of only one row, where all $$$26$$$ lowercase Latin letters will be arranged in some order.Polycarp uses the same password $$$s$$$ on all websites where he is registered (it is bad, but he doesn't care). He wants to assemble a keyboard that will allow to type this password very easily. He doesn't like to move his fingers while typing the password, so, for each pair of adjacent characters in $$$s$$$, they should be adjacent on the keyboard. For example, if the password is abacaba, then the layout cabdefghi... is perfect, since characters a and c are adjacent on the keyboard, and a and b are adjacent on the keyboard. It is guaranteed that there are no two adjacent equal characters in $$$s$$$, so, for example, the password cannot be password (two characters s are adjacent).Can you help Polycarp with choosing the perfect layout of the keyboard, if it is possible?

Input: The first line contains one integer $$$T$$$ ($$$1 \le T \le 1000$$$) — the number of test cases.Then $$$T$$$ lines follow, each containing one string $$$s$$$ ($$$1 \le |s| \le 200$$$) representing the test case. $$$s$$$ consists of lowercase Latin letters only. There are no two adjacent equal characters in $$$s$$$.

Output: For each test case, do the following:  if it is impossible to assemble a perfect keyboard, print NO (in upper case, it matters in this problem);  otherwise, print YES (in upper case), and then a string consisting of $$$26$$$ lowercase Latin letters — the perfect layout. Each Latin letter should appear in this string exactly once. If there are multiple answers, print any of them. 


Sample Inputs:
5
ababa
codedoca
abcda
zxzytyz
abcdefghijklmnopqrstuvwxyza

Sample Outputs:
YES
bacdefghijklmnopqrstuvwxyz
YES
edocabfghijklmnpqrstuvwxyz
NO
YES
xzytabcdefghijklmnopqrsuvw
NO

Solution (Python):
def perfect_keyboard_layout(s):
    l = ''
    index = 0
    flag = 0
    for c in s:
        if c not in l:
            if len(l) - 1 == index:
                l += c
                index = len(l) - 1
            elif index == 0:
                l = c + l
            else:
                flag = 1
                break
        elif index - 1 >= 0 and l[index - 1] == c:
            index -= 1
        elif index + 1 < len(l) and l[index + 1] == c:
            index += 1
        else:
            flag = 1
            break
    if flag:
        return 'NO'
    else:
        alphabet = ''.join((chr(j) for j in range(ord('a'), ord('z') + 1) if chr(j) not in l))
        return f'YES\n{l}{alphabet}'
m = int(input())
for _ in range(m):
    s = input().strip()
    result = perfect_keyboard_layout(s)
    print(result)

Solution (Python):
def ss(s):
    n = len(s)
    ans = ['.'] * 70
    i = 35
    d = {}
    for x in s:
        if x in d:
            if ans[i - 1] == x:
                i -= 1
            elif ans[i + 1] == x:
                i += 1
            else:
                return 'NO'
        elif ans[i + 1] == '.':
            i += 1
            ans[i] = x
            d[x] = 1
        elif ans[i - 1] == '.':
            i -= 1
            ans[i] = x
            d[x] = 1
        else:
            return 'NO'
    while ans[0] == '.':
        ans = ans[1:]
    while ans[-1] == '.':
        ans = ans[:-1]
    for i in range(26):
        if chr(i + ord('a')) not in d:
            ans += chr(i + ord('a'))
    return ans
for _ in range(int(input())):
    s = str(input())
    ans = ss(s)
    if ans == 'NO':
        print(ans)
    else:
        print('YES')
        print(''.join(ans))

Solution (Python):
import string

def solve():
    G = int(input())
    for H in range(G):
        E = input().strip()
        A = []
        A.append(E[0])
        C = 0
        D = set(A)
        F = False
        for B in E[1:]:
            if C > 0 and B == A[C - 1]:
                C -= 1
            elif C < len(A) - 1 and B == A[C + 1]:
                C += 1
            elif C == len(A) - 1 and B not in D:
                A.append(B)
                D.add(B)
                C += 1
            elif C == 0 and B not in D:
                A = [B] + A
                D.add(B)
            else:
                F = True
        if F:
            print('NO')
        else:
            print('YES')
            for B in string.ascii_lowercase:
                if B not in D:
                    A.append(B)
            print(''.join(A))
if __name__ == '__main__':
    solve()