Palindrome

Interview

Time limit1sMemory limit256 MB

Summary

Given a string, find the minimum number of characters to insert anywhere so the string becomes a palindrome.

Level: Medium6 of 10
Topics: Dynamic programming, String, Two pointers, Recursion
Solved: No attempts yet

Problem

A palindrome is a symmetric string: it reads the same from left to right as from right to left. Given a string, you may insert characters into it to turn it into a palindrome. Write a program that finds the minimum number of characters you must insert.

For example, the string "Ab3bd" can be turned into a palindrome such as "dAb3bAd" or "Adb3bdA" by inserting 2 characters, and it cannot be made into a palindrome by inserting fewer than 2. So the answer is 2 in this case.

An inserted character may be placed at any position in the string.

Input

The first line contains the length of the string $N$ ( $3 \le N \le 5000$ ). The second line contains a string of length $N$ . The string consists of uppercase letters 'A'–'Z', lowercase letters 'a'–'z', and digits '0'–'9'. Uppercase and lowercase letters are treated as distinct.

Output

Print the minimum number of characters that must be inserted to make the string a palindrome.

Examples1

Example 1
Input
```
5
Ab3bd
```
Expected output
```
2
```