Palindrome Partitioning III

You are given a string s containing lowercase letters and an integer k. You need to :

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:


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;
    }
}