DNA 문자열

시간 제한2초메모리 제한512 MB

요약

DNA 문자열 S가 주어질 때, S의 연속 부분 문자열로 나타나지 않는 가장 짧은 A, C, G, T 문자열을 찾고, 여러 개면 사전순으로 가장 앞선 것을 출력한다.

난이도: 보통10점 중 5점
유형: 문자열, 문자열 매칭, 완전 탐색
정답자: 아직 제출이 없습니다

문제

DNA는 A, C, G, T로만 이루어진 문자열이다.

영선이는 인간 유전자를 연구하려고 생물학자 효빈이를 고용했다. 효빈이가 연구하는 DNA는 문자열 $S$ 이다. 효빈이는 $S$ 안에 연속으로 등장하지 않는 가장 짧은 DNA 문자열을 찾으려고 한다.

길이가 가장 짧은 답이 여러 개일 수 있다. 그런 경우에는 사전 순으로 가장 앞선 문자열 하나만 정답으로 인정한다. 문자의 크기 순서는 A, C, G, T이다.

예를 들어 $S$ = "AGGTCTA"를 보자. 길이가 1인 문자열 A, C, G, T는 모두 $S$ 에 등장하므로 답의 길이는 2 이상이다. 길이가 2인 문자열 중 "AA"는 $S$ 에 등장하지 않고, 사전 순으로 "AA"보다 앞선 길이 2짜리 문자열은 없으므로 답은 "AA"이다. "AG"는 $S$ 에 등장하므로 답이 될 수 없고, "AAA"는 길이가 2인 답이 있으므로 답이 될 수 없다.

$S$ 가 주어졌을 때 답을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 $S$ 가 주어진다. $S$ 는 A, C, G, T로만 이루어져 있고, 길이는 1 이상 2,000 이하이다.

출력

첫째 줄에 $S$ 안에 연속으로 등장하지 않는 가장 짧은 DNA 문자열을 출력한다. 그런 문자열이 여러 개면 사전 순으로 가장 앞선 것을 출력한다. 문자의 크기 순서는 A, C, G, T이다.

예제4

예제 1
입력
```
AGGTCTA
```
예상 출력
```
AA
```
예제 2
입력
```
AGACGACGGAGAACGA
```
예상 출력
```
T
```
예제 3
입력
```
A
```
예상 출력
```
C
```
예제 4
입력
```
AAGATACACCGGCTTCGTG
```
예상 출력
```
AAA
```