The following question is taken from leetcode: 1278. Palindrome Partitioning III

You are given a string $s$ containing lowercase letters and an integer $k$. You need to:

  1. First, change some characters of $s$ to other lowercase English letters.
  2. Then, divide $s$ into $k$ non-empty disjoint substrings such that each substring is a palindrome.

Return the minimal number of characters that you need to change to divide the string.

So I did find the cost array to make a string to a palindrome. Something like below:

[('bcccdefg', 4), ('ccde', 2), ('ccdef', 2), ('ef', 1)] # (character, cost to make it a palindrome)

I am thinking whether this can be done using knapsack recurrence relations, where profit will be cost and weight will be length of the substring; the total backpack weight will be the length of the main string. Though I am not sure what to do with $k$. Do I need 3 states, or are 2 states enough?

Is my thinking correct? If no, what is the right way to write a recurrence relation for this?


1 Answer 1


Let $s=s_1 s_2 \dots s_n$. Suppose that you already know, for each substring $s[i:j]=s_is_{i+1}\dots s_k$ of $s$, the minimum number $D(i,j) $ of character substitutions needed to make $s[i:j]$ palindrome. These values can be found in $O(n^2)$ time using dynamic programming since $D(i,j) = 0$ if $i>j$ and $D(i,j) = D(i+1,j-1) + \mathbb{1}_{s_i \neq s_j}$ if $i \le j$.

Your problem exhibits the optimal substructure property. Suppose that you already known the beginning position $i$ of the last substring $s[i:n]$ of $s$ in an optimal partition: clearly you will need to make $D(i,n)$ changes in order to transform $s[i:n]$ into a palindrome. You are then left with the prefix $s[1:i-1]$ of $s$. This prefix still needs to be partitioned into $k-1$ nonempty substrings that are palyndromes. Fortunately this is exactly an instance of the problem you were trying to solve in the first place. You can exploit this property as follows:

Define $OPT[j,h]$ as the minimum number of character substitutions needed in order to partition $s[1:j]$ into $h$ substrings, each of which is non-empty and palindrome. If no such partition can exist, regardless of the number of character substitutions, let $OPT[j,h]=+\infty$.

By definition $OPT[0,0]=0$ (since $s[1:0]$ is the empty string) and, for $h=1,\dots,k$, $D[0,h] = +\infty$.

Moreover, for $i=1,\dots,n$ and $h=1, \dots, k$: $$ OPT[j,h] = \min_{i=1,\dots,j} \left\{ OPT[i-1,h-1] + D(i, j) \right\}. $$

This gives you a dynamic programming algorithm with time complexity $O(k n^2)$. The optimal solution to your original problem is $OPT[n,k]$.

  • $\begingroup$ thanks, Steven. It totally makes sense now. Anyway, can you please add a couple of sentences on what was your first thought to come up with a recurrence solution for this problem? do you have any common strategy to find a recurrence relation for a problm? $\endgroup$
    – Amin Ahmed
    Apr 17, 2020 at 16:00
  • $\begingroup$ I added a brief description of the intuition behind the algorithm. I am not aware of any "one catches all" strategy to find a subproblem definition that allows subproblems to be recursively recombined. If you are lucky, the subproblem instances will just be "smaller" versions of your original instance. This is indeed the case for this problem: we are just looking at all prefixes of $s$ and at all smaller values of $k$. $\endgroup$
    – Steven
    Apr 17, 2020 at 16:14
  • $\begingroup$ yeah, you are right mate. Thanks a lot for the answer! Cheers! $\endgroup$
    – Amin Ahmed
    Apr 17, 2020 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.