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.

Failed to build the dp during the contest : ( .   it was quite close

class Solution {
    public int palindromePartition(String s, int k) {
        if (k == s.length()){
            return 0;
        }
        
        int[][] dp = new int[s.length()+1][k+1];
        
        
        for (int i = 0; i <= s.length(); i++)
            for (int j = 0; j <= k; j++)
                dp[i][j] = s.length();
        
        dp[0][0] = 0;
        for (int i = 0; i < s.length(); i ++){
          
            for (int j = 0; j < k; j ++){
                
                for (int len = 1; i + len <= s.length(); len++) {
                    int cost = 0;

                    for (int a = i, b = i + len - 1; a < b; a++, b--){
                        if (s.charAt(a) != s.charAt(b)){
                            cost ++;
                        }
                    }
    

                    dp[i + len][j + 1] = Math.min(dp[i + len][j + 1], dp[i][j] + cost);
                }
            }
        }
        
        return dp[s.length()][k];
    }
    

}

Few things to point out:

• I initialize each value of dp with s.length(), since it can’t be worse than replacing every chars. Integer.MAX_VALUE will cause an integer overflow while building the dp