Palindrome Partitioning

Time limit2sMemory limit128 MB

Summary

Given an uppercase string up to length 2500, compute the minimum number of pieces to cut it into palindromic substrings.

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

Problem

A given string should be divided into several palindromic substrings. For example, ABACABA can be divided as {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, or {ABACABA}.

Find the minimum number of pieces needed to divide the entire string into palindromic substrings.

Input

The first line contains a string consisting only of uppercase English letters. Its length is at most 2,500.

Output

Print the minimum number of pieces in a palindrome partition of the string.

Examples4

Example 1
Input
```
BBCDDECAECBDABADDCEBACCCBDCAABDBADD
```
Expected output
```
22
```
Example 2
Input
```
AAAA
```
Expected output
```
1
```
Example 3
Input
```
ABCDEFGH
```
Expected output
```
8
```
Example 4
Input
```
QWERTYTREWQWERT
```
Expected output
```
5
```