A string of characters is a palindrome if the sequence is the same read forward as backward. In this question you will solve some problems related to palindrome strings. In the following question, find the appropriate recursion and pseudocode, describe the algorithm and analyze its running time.

Given a string, we want to delete its characters by deleting a substring which is a palindrome in each iteration. Note, that a single character is a palindrome of length 1. After deleting a substring the remaining parts are concatenated. Find the minimum number of such deletions to delete the entire string. For example, the string 23456542 can be deleted in two iterations. First, delete 45654, then what is remaining is 232 which is deleted in the second iteration.