favorite We need a little bit of your help to keep things running, click on this banner to learn more

Dynamic programming

Cut a string

You are given a string s. It is allowed to take any two same neighbor symbols of this string and delete them. This operation you can do while possible. At the beginning you can choose any symbols from string and delete them. Determine the minimum number of symbols you can delete at the beginning, so that you get the empty string after performing allowed operations.


One string s of length no more than 100.


Print the minimum number of symbols you should delete at the beginning.

Time limit 1 second
Memory limit 128 MiB
Input example #1
Output example #1
Source 2014 KBTU Open, Spring Kazakhstan, Almaty, April 20, Problem J