Loading problem…
You are given a string `s` containing lowercase letters and an integer `k`. You need to: - First, change some characters of `s` to other lowercase English letters. - 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.
Example 1
Input: s = abc, k = 2
Output: 1
Explanation: Split into 2 palindromic parts, e.g. "a" | "bc"; making "bc" a palindrome costs 1 change.
Example 2
Input: s = aabbc, k = 3
Output: 0
Explanation: "aa" | "bb" | "c" are already palindromes, so 0 changes are needed.
Example 3
Input: s = bookcase, k = 8
Output: 0
Explanation: k = 8 equals the length of the string, so every character becomes its own one-letter palindrome and no changes are needed.
Precompute cost[i][j] = characters to change to make s[i..j] a palindrome. Then dp[i][j] = min changes to split the first i characters into j palindromic parts, choosing where the last part begins.
Run checks all cases above. Submit evaluates all test cases.