IOI '00 P1 - Palindrome

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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.