Given a string s and an integer k, partition s into exactly k non-empty palindromic substrings using the minimum number of character changes. Return that minimum number of changes. Pattern focus: Palindrome partitioning. This problem combines interval palindrome cost computation with partition DP.
s = input string, k = number of palindromic parts
minimum number of character changes
Example 1:
Input:
s = "abc" k = 2
Output:
1
Explanation:
One optimal split is a | bc, and bc needs one change to become a palindrome.
Example 2:
Input:
s = "aabbc" k = 3
Output:
0
Explanation:
Split as aa | bb | c, all of which are already palindromes.