시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 165 78 65 57.018%

문제

팰린드롬이란 대칭 문자열이다. 즉, 왼쪽에서 오른쪽으로 읽었을때와 오른쪽에서 왼쪽으로 읽었을때 같다는 얘기다. 당신은 문자열이 주어졌을때, 최소 갯수의 문자를 삽입하여 팰린드롬이 되게 되는 문자의 갯수를 구하는 프로그램을 작성하여라.

예제에서는, 2개의 문자를 삽입하여 팰린드롬이 된다. "Ab3bd"는 "dAb3bAd" 혹은 "Adb3bdA" 로 바뀔 수 있다. 하지만, 2개 미만의 문자를 삽입해서는 팰린드롬이 될 수 없다.

입력

첫번째 줄에는 문자열의 길이 N (3<=N<=5000)이 주어진다. 두번째 줄에는 길이가 N인 문자열이 주어진다. 문자열은 대문자 'A'~'Z'와 소문자 'a'~'z', 숫자 0~9로 이루어진다. 대문자와 소문자는 구분되어야 한다.

출력

첫번째 줄에 삽입해야할 최소 갯수를 출력한다.

예제 입력

5
Ab3bd

예제 출력

2

힌트

출처

Olympiad > International Olympiad in Informatics > IOI 2000 1번