IOIPALIN  Palindrome 2000
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
The first line contains one integer: the length of the input string N, 3≤N≤5000. 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
The first line contains one integer, which is the desired minimal number.
Example
Input: 5 Ab3bd Output: 2
hide comments
Divyank Duvedi:
20141019 08:18:18
no space optimisation is required :) 

AKASH GOEL:
20140825 21:55:44
space optimization is the key to AC!


mohsin mohammad:
20140811 19:09:21
happy DP :) AC! 

Sachin Malhotra:
20140727 23:53:05
ummm.. In Love with DP :) :)..


Sachin Malhotra:
20140727 22:30:22
Bottom up also giving TLE :( Last edit: 20140727 22:58:12 

Mohamed Essam:
20140609 11:44:58
Changed variable names, got AC _ 

Ashwini:
20140602 11:15:48
learnt a new thing. didnt know crucial can space optimisation prove at times :) 

Rishav Goyal:
20140524 11:52:16
try to optimize N^2 with abit calculation > AC with 7.! 

sai madan mohan reddy:
20140320 19:11:26
getting SIGSEGV at 0.91 secs any help 

innovolt:
20140317 04:00:44
another space optimization problem similar concept problem is LKS.....overall gud1 learnt a lot thanxx spoj 
Added by:  Gareev 
Date:  20100816 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC PERL6 VB.NET 
Resource:  IOI 2000, Day 1 