Recall that a palindrome is any string that is exactly the same as its reversal, like I, or DEED, or RACECAR, or . For technical reasons, in this problem, we will only be interested in palindromes that are of length at least one, hence we will not treat the string as a palindrome. Any string can be decomposed into a sequence of palindrome substrings. For example, the string
BUBBASEESABANANA ("Bubba sees a banana.") can be broken into palindromes in the following ways (among many others):
BUB BASEESAB ANANA
B U B B A S E E S A B ANA N A
B U B B A S E E S A B A N A N A
Since any string w can always be decomposed to palindromes we may want to find a de- composition that optimizes some objective. Here are two example objectives. The first objective is to decompose w into the smallest number of palindromes. A second objective is to find a decomposition such that each palindrome in the decomposition has length at least k where k is some given input parameter. Both of these can be cast as special cases of an abstract problem Suppose we are given a function called cost) that takes a positive integer h as input and outputs an integer cost(h). Given a decomposition of w into u1,U2,...,ur (that is, w uUur) we can define the cost of the decomposition as Σί-i cost(w)
For example if we define cost(h) - 1 for all h 2 1 then finding a minimum cost palindromic decomposition of a given string w is the same as finding a decomposition of w with as few palindromes as possible. Suppose we define cost) as follows: cost(h) - 1 for h < k and cost(h)-0 for h 2 k. Then finding a minimum cost palindromic decomposition would enable us to decide whether there is a decomposition in which all palindromes are of length at least k; it is possible iff the minimum cost is 0.
Describe an efficient algorithm that given black box access to a function cost), and a string w outputs the value of a minimum cost palindromic decomposition of w.