This is typically a dynamic programming problem with 2 dimensional (one is the string length and another is the k).
Let's say, to split s[:hi + 1] into k palindrome strings, we need at least change dp(hi, k) characters. Then, dp(hi, k) = min( dp(i, k - 1) for i in range(k - 2, hi) ).
One difficult part is the range for i is from k - 2 to hi, this is because k < hi + 1.
class Solution:
def numChanges(self, lo, hi):
count = 0
while hi > lo:
if self.s[hi] != self.s[lo]:
count += 1
hi -= 1
lo += 1
return count
def dp(self, hi, k):
if self.cache[hi][k] is None:
if k == 1:
self.cache[hi][k] = self.numChanges(0, hi)
else:
self.cache[hi][k] = min(
[(self.dp(i, k - 1) + self.numChanges(i + 1, hi)) for i in range(k - 2, hi)]
)
return self.cache[hi][k]
def palindromePartition(self, s: str, k: int) -> int:
n = len(s)
self.cache = [[None] * (k + 1) for _ in range(n)]
self.s = s
return self.dp(n - 1, k)