Palidrome

Dynamic Programming

A palindrome is a string that reads the same forwards and backwards, like x, pop, noon, redivider. Any string can be broken into sequence of palindromes. For example, the string bubbaseesabanana (‘bubba sees a banana’) can be broken into palindromes in several different ways:

• bub baseesab anana
• b u bb a sees a b anana
• b u b b a s e e s a b a n a n a

Find the minimum number of palindromes that make up the given string

Input format: first line is a single number n, the following line consists of length n string (character array) that is the string A[1..n]

Example 1

Input:
16
bubbaseesabanana

Output:
3