IOI '00 P1 - Palindrome

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 32M

Problem type

A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a program which, given a string, determines the minimal number of characters to be inserted into the string in order to obtain a palindrome.

As an example, by inserting 2 characters, the string Ab3bd can be transformed into a palindrome (dAb3bAd or Adb3bdA). However, inserting fewer than 2 characters does not produce a palindrome.

Input Specification

The first line contains one integer: the length of the input string N, 3 \le N \le 5\,000. The second line contains one string with length N. The string is formed from uppercase letters from A to Z, lowercase letters from a to z and digits from 0 to 9. Uppercase and lowercase letters are to be considered distinct.

Output Specification

The first line contains one integer, which is the desired minimal number.

Sample Input

5
Ab3bd

Sample Output

2

Comments

There are no comments at the moment.