1
class Solution {
2
  public int mismatchCount(String s) {
3
    int n = s.length() - 1;
4
    int count = 0;
5
    for (int i = 0, j = n; i < j; i++, j--) {
6
      if (s.charAt(i) != s.charAt(j)) count++;
7
    }
8
    return count;
9
  }
10

11
  public int helper(String s, int n, int i, int j, int k, Integer[][][] dp) {
12
    if (j >= n) return 105;
13
    if (k < 0) return 105;
14
    if (dp[i][j][k] != null) {
15
      return dp[i][j][k];
16
    }
17
    if (n - j < k) return dp[i][j][k] = 105;
18
    if (n - j == k) return dp[i][j][k] = mismatchCount(s.substring(i, j + 1));
19
    int stop = mismatchCount(s.substring(i, j + 1)) + helper(s, n, j + 1, j + 1, k - 1, dp);
20
    int cont = helper(s, n, i, j + 1, k, dp);
21
    return dp[i][j][k] = Math.min(stop, cont);
22
  }
23

24
  public int palindromePartition(String s, int k) {
25
    int n = s.length();
26
    Integer[][][] dp = new Integer[n][n][k + 1];
27
    return helper(s, s.length(), 0, 0, k, dp);
28
  }
29
}