JAVA Solution || Recurison-->Memoized
Intuition\n Describe your first thoughts on how to solve this problem. \nsolution is same as palindrome partitioning ,slight difference is that issubstring is n
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nsolution is same as palindrome partitioning ,slight difference is that issubstring is not palindrome count no of characters to change.\n\n\n# Complexity\n- Time complexity:O(N*N*K)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(N*K)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int palindromePartition(String s, int k) {\n        int n=s.length();\n        if(k>=n)return 0;\n        long dp[][]=new long[n+1][k+1];\n        for(long[] r:dp)Arrays.fill(r,-1);\n        return (int)solve(s,k,0,n,dp);\n    }\n    public long solve(String s,int k,int i,int n,long[][] dp){\n        if(k==0 && i==n)return 0;\n        if(k<=0 || i>=n)return Integer.MAX_VALUE;\n        if(dp[i][k]!=-1)return dp[i][k];\n        long ans=Integer.MAX_VALUE;\n        for(int j=i+1;j<=n;j++){\n            int count=isPalindrome(s.substring(i,j));\n            if(count==0)ans=Math.min(ans,solve(s,k-1,j,n,dp));\n            else ans=Math.min(ans,count+solve(s,k-1,j,n,dp));\n        }\n        if(dp[i][k]!=-1)\n        return dp[i][k]=Math.min(dp[i][k],ans);\n        else return dp[i][k]=ans;\n    }\n    public int isPalindrome(String s){\n        int i=0;\n        int j=s.length()-1;\n        int count=0;\n        while(i<j){\n         if(s.charAt(i)!=s.charAt(j))count++;\n         i++;\n         j--;\n        }\n        return count;\n    }\n}\n```
['Dynamic Programming', 'Recursion', 'Java']