(Java) 2d DP with preprocessing (Less than 98% )
The array here stores the number of characters to be changed for all substrings in the given string to become palindromes.\n\n    static int len;\n    static in
The array here stores the number of characters to be changed for all substrings in the given string to become palindromes.\n```\n    static int len;\n    static int[][] arr;\n    static int[][] dp;\n    public int palindromePartition(String s, int k) {\n        \n         len=s.length();\n        \n        arr = new int[len][len];\n        dp=new int[len+1][k+1];\n        for(int i=0;i<len+1;i++){\n            for(int j=0;j<k+1;j++){\n                dp[i][j]=-1;\n            }\n        }\n        for(int gap=0;gap<len;gap++){\n            for(int i=0;i<len-gap;i++){\n                int j=i+gap;\n                if(gap==0){\n                    arr[i][j]=0;\n                }else if(gap==1){\n                    arr[i][j]=(s.charAt(i)==s.charAt(j))?0:1;\n                }else{\n        arr[i][j]=(s.charAt(i)==s.charAt(j))?arr[i+1][j-1]:1+arr[i+1][j-1];}}}\n        \n        \n        return func(k,0);\n    }\n    \n    \n    static int func(int k, int ind){\n        if(ind==len||ind!=len && k==0){\n\t\t\t\treturn len;\n\t\t}\n        if(k==1){\n            return arr[ind][len-1];\n        }\n        if(dp[ind][k]!=-1)return dp[ind][k];\n        int ans=len;\n        for(int i=ind;i<len;i++){\n            ans=Math.min(ans,arr[ind][i]+func(k-1,i+1));\n        }\n        dp[ind][k]=ans;\n        return ans;\n    }\n    ```\n
[]