Minimal number of changes to make string into concatenation of $k$ palindromes

Question

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?

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]$.