제곱 단어

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

요약

소문자 문자열이 주어질 때, 남은 글자가 순서를 유지한 채 xx 형태의 제곱 단어가 되도록 지워야 하는 최소 글자 수를 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 문자열
정답자: 아직 제출이 없습니다

문제

제곱 단어(squared word)는 $xx$ 꼴의 단어, 즉 어떤 문자열을 두 번 이어 붙인 형태의 단어입니다. 예를 들어 영어 단어 couscous, murmur(낮게 이어지는 소리), tartar(굳은 치석), hotshots 는 모두 제곱 단어입니다.

주어진 단어에서 문자 몇 개를 지워 제곱 단어로 만들려고 합니다. 완성된 단어가 실제로 존재하는 영어 단어일 필요는 없습니다. 문자를 지운 뒤 남은 문자들은 원래 순서를 그대로 유지합니다. 이때 지워야 하는 문자의 최소 개수를 구하세요.

입력

첫째 줄에 단어의 길이를 나타내는 정수 $n$ ( $1 \le n \le 1000$ )이 주어집니다. 둘째 줄에 소문자 알파벳 $n$ 개로 이루어진 단어가 주어집니다.

출력

단어를 제곱 단어로 만들기 위해 지워야 하는 문자의 최소 개수를 정수 하나로 출력합니다. 빈 단어도 올바른 제곱 단어로 간주합니다.

힌트

예를 들어 단어 tachystoskopach에서 y, s, o, s, k, o, p를 지우면 제곱 단어 tachtach가 됩니다. (폴란드어에서 tachtach는 잘 알려지지 않은 마차의 한 종류를 뜻합니다.)

예제3

예제 1
입력
```
15
tachystoskopach
```
예상 출력
```
7
```
예제 2
입력
```
8
couscous
```
예상 출력
```
0
```
예제 3
입력
```
3
abc
```
예상 출력
```
3
```