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 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: You can split the string into "ab" and "c", and change 1 character in "ab" to make it palindrome.
Example 2:
Input: s = "aabbc", k = 3
Output: 0
Explanation: You can split the string into "aa", "bb" and "c", all of them are palindrome.
Example 3:
Input: s = "leetcode", k = 8
Output: 0
Constraints:
1 <= k <= s.length <= 100.
s only contains lowercase English letters.
Solution:
class Solution {
Integer[][] dp;
public int palindromePartition(String s, int k) {
dp = new Integer[k + 1][s.length() + 1];
return helper(s, k, 0);
}
private int helper(String s, int k, int curr) {
if (curr == s.length() && k == 0) return 0;
if (curr == s.length() || k == 0) return s.length();
if (dp[k][curr] != null) return dp[k][curr];
int n = s.length();
int res = n;
for (int i = curr; n - i >= k; i ++) {
String sub = s.substring(curr, i + 1);
int p = change(sub);
// System.out.println(sub + ", " + p);
res = Math.min(res, p + helper(s, k - 1, i + 1));
}
return dp[k][curr] = res;
}
private int change(String s) {
int count = 0;
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
count ++;
}
left ++;
right --;
}
return count;
}
}