Palindrome Partition

Time limit2sMemory limit128 MB

Summary

Given a lowercase string up to length 2000, find the minimum number of palindromic substrings it can be partitioned into.

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

Problem

A palindrome is a word that reads the same from left to right and from right to left. Words such as aba and a are palindromes, while abaccbcb and anavolimilana are not.

A word that is not itself a palindrome can be split into several palindromic substrings. Given a word, split it so that every piece is a palindrome and the number of pieces is as small as possible.

For instance, abaccbcb can be split into aba, cc, and bcb, so the answer is 3. It cannot be split into only two palindromic pieces. Likewise, anavolimilana can be split into ana, v, o, limil, and ana, so the answer is 5.

Write a program that prints the minimum number of palindromic substrings needed to partition the given word. If the whole word is already a palindrome, it does not need to be split.

Input

The first line contains one word. The word consists only of lowercase English letters, and its length is at most 2,000.

Output

Print the minimum number of palindromic substrings into which the given word can be split.

Examples3

Example 1
Input
```
anaban
```
Expected output
```
2
```
Example 2
Input
```
abaccbcb
```
Expected output
```
3
```
Example 3
Input
```
anavolimilana
```
Expected output
```
5
```