B. Prinzessin der Verurteilung #724 Div.2

https://codeforces.com/contest/1536/problem/B
시간 2초, 메모리 256MB

input :

• t (1≤t≤1000)
• n (1≤n≤1000)

output :

• For each test case, output the MEX of the string on a new line.
  각 테스트 케이스에서의 MEX를 출력하시오.

조건 :

• The MEX of the string is defined as the shortest string that doesn't appear as a contiguous substring in the input.
  MEX는 가장 작은 연속된 부분문자열 중에서 등장하지 않은 것을 뜻한다.

• If multiple strings exist, the lexicographically smallest one is considered the MEX. Note that the empty substring does NOT count as a valid MEX.
  여러 개가 존재한다면, 사전순으로 가장 작은것을 MEX로 취급한다.(빈 문자열은 MEX로 생각하지 않는다.)

어마무시하다...
일단 부분문자열로 가능한 모든 경우들을 따져보도록 하자.
길이가 1일 때 -> 26가지.
길이가 2일 때 -> 26 * 26가지.
길이가 3일 떄 -> 26 * 26 * 26 가지 == 17576

입력받는 문자열의 가장 긴 길이는 1000
부분 문자열로 길이가 3이라 지정했을 때 얻을 수 있는 경우의 수는 998개.

결국 길이가 3인 모든 부분문자열을 확인 할 수가 없다. 확인해야 할 경우의 수 자체가 26 + 26^2 + 26^3 인 것이다.

입력 받은 문자열에서 가능 한 모든 부분 문자열 길이가 1, 2, 3인 것을 딕셔너리에 저장을 한 후에 하나씩 찾도록 하자...

길이가 1.

for j in range(26):
        word = chr(j + 97)
        if word not in data:
            return word

아스키 코드를 사용해서 저렇게 만들게 된다면 word에 문자열을 저장 할 수 있다.
작성한 코드에서는 그냥 리스트에 존재하는지를 확인하도록 했는데 길이가 최대 1000이여서인지 시간 복잡도는 괜찮았다.

길이가 2.

    for j in range(26):
        for k in range(26):
            word = chr(j + 97) + chr(k + 97)
            if word not in data:
                return word

chr() + chr() 으로 문자열을 만들 수 있다.

길이가 3.

    for j in range(26):
        for k in range(26):
            for l in range(26):
                word = chr(j + 97) + chr(k + 97) + chr(l + 97)
                if word not in data:
                    return word

모든 경우의 수가 20000이 안 되기 때문에 괜찮다.

# from r-tron18's solution
import sys


def check():
    for j in range(26):
        word = chr(j + 97)
        if word not in data:
            return word

    for j in range(26):
        for k in range(26):
            word = chr(j + 97) + chr(k + 97)
            if word not in data:
                return word

    for j in range(26):
        for k in range(26):
            for l in range(26):
                word = chr(j + 97) + chr(k + 97) + chr(l + 97)
                if word not in data:
                    return word

t = int(sys.stdin.readline())
for i in range(t):
    n = int(sys.stdin.readline())
    data = sys.stdin.readline().rstrip()
    print(check())