탈출 방

면접 대비

시간 제한1초메모리 제한1024 MB

요약

힌트 문자열에서 RAKTAS를 부분 수열로 포함하는 가장 짧은 접두사의 길이를 구합니다.

문제

리투아니아 정보올림피아드 30주년을 기념하여 평가위원회 위원들이 스스로를 위한 놀이로 탈출 방을 만들었다. 탈출 방은 각각 대문자 라틴 문자로 표시된 힌트들의 순서이다.

힌트는 첫 번째부터 마지막까지 하나씩 차례로 공개된다. 위원들은 모은 힌트를 배열해 단어 RAKTAS를 만들 수 있으면 방에서 탈출할 수 있다.

힌트 순서가 RAUDONASNYKSTUKAS인 탈출 방을 생각해 보자. 위원들은 힌트 13개를 풀면 탈출할 수 있다.

RAUDONASNYKSTUKAS

마지막 힌트 네 개(회색으로 표시)는 필요하지 않다. 이미 모은 힌트로 RAKTAS를 만들 수 있기 때문이다(대응하는 글자는 밑줄로 표시).

방에서 탈출하려면 최소 몇 개의 힌트를 공개해야 하는지 구하는 프로그램을 작성하라.

첫째 줄에 힌트의 개수 $N$ 이 주어진다.

둘째 줄에는 힌트의 순서를 나타내는 길이 $N$ 의 문자열이 주어진다. 각 힌트는 A부터 Z까지의 대문자 라틴 문자로 표시된다. 문자열에는 다른 문자가 없다.

필요한 힌트의 최소 개수를 정수 하나로 출력한다.

입력은 항상 답이 존재하도록 주어진다.

$1 ≤ N ≤ 100$