Simple recursive solution with memoization.
\nclass Solution {\n    public int palinCheck(String s, int start, int end) {\n        int ct = 0;\n        while (start < end) {\n            if (s.charAt(star
```\nclass Solution {\n    public int palinCheck(String s, int start, int end) {\n        int ct = 0;\n        while (start < end) {\n            if (s.charAt(start) != s.charAt(end)) ct++;\n            start++;\n            end--;\n        }\n        \n        return ct;\n    }\n    \n\n    public int divide(int pos, int start, String s, int k, int[][][] memo) {\n        if (pos == s.length()) {\n            if (k == 0 && start == s.length()) {\n                return 0;\n            }\n            return 100; // max number of characters to change = s.length\n        }\n\n        if (memo[pos][start][k] != -1) return memo[pos][start][k];\n                \n        int continue_partition = divide(pos+1, start, s, k, memo);\n        int new_partition = Integer.MAX_VALUE;\n        if (k-1 >= 0) {\n            new_partition = palinCheck(s, start, pos) + divide(pos+1, pos+1, s, k-1, memo);\n        }\n        \n        return memo[pos][start][k] = Math.min(continue_partition, new_partition);     \n    }\n\n    public int palindromePartition(String s, int k) {\n        int n = s.length();\n        int[][][] memo = new int[n+1][n+1][k+1];\n        for (int[][] level1: memo) {\n            for (int[] level2 : level1) {\n                Arrays.fill(level2, -1);\n            }\n        }\n        \n        return divide(0, 0, s, k, memo);\n    }\n}\n```
[]