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 a palindrome.


Return the minimal number of characters that you need to change to divide the string.

&nbsp;
Example 1:

Input: s = "abc", k = 2
Output: 1
Explanation:&nbsp;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:&nbsp;You can split the string into "aa", "bb" and "c", all of them are palindrome.

Example 3:

Input: s = "leetcode", k = 8
Output: 0


&nbsp;
Constraints:


	1 &lt;= k &lt;= s.length &lt;= 100.
	s only contains lowercase English letters.


class Solution:
    def palindromePartition(self, s: str, t: int) -> int:
        n=len(s)
        @lru_cache(None)
        def is_palin(s):                #This function returns min no of chars to change to make s as a palindrome
            cnt=0
            for c1,c2 in zip(s,s[::-1]):
                if c1!=c2: cnt+=1
            if len(s)%2==0:
                return cnt//2
            return (cnt+1)//2
        @lru_cache(None)
        def dp(i,j,k):            #We analyse string s[i:j+1] with k divisions left
            if j==n:
                return 0 if k==0 else sys.maxsize
            if k==0: 
                return sys.maxsize
            ans=sys.maxsize
            cnt=is_palin(s[i:j+1])
            #terminate here
            ans=min(ans,dp(j+1,j+1,k-1)+cnt)
            #dont terminate
            ans=min(ans,dp(i,j+1,k))
            return ans
        return dp(0,0,t)
                        
                
            
class Solution {
    public int mismatchCount(String s) {
        int n = s.length()-1;
        int count = 0;
        for(int i=0,j=n;i<j;i++,j--) {
            if(s.charAt(i) != s.charAt(j))
                count++;
        }
        return count;
    }
    public int helper(String s, int n, int i, int j, int k, Integer[][][] dp) {
        if(j>=n)
            return 105;
        if(k<0)
            return 105;
        if(dp[i][j][k] != null) {
            return dp[i][j][k];
        }
        if(n-j<k)
            return dp[i][j][k] = 105;
        if(n-j==k)
            return dp[i][j][k] = mismatchCount(s.substring(i,j+1));
        int stop = mismatchCount(s.substring(i,j+1)) + helper(s,n,j+1,j+1,k-1,dp);
        int cont = helper(s,n,i,j+1,k,dp);
        return dp[i][j][k] = Math.min(stop, cont);
    }
    public int palindromePartition(String s, int k) {
        int n = s.length();
        Integer[][][] dp = new Integer[n][n][k+1];
        return helper(s,s.length(),0,0,k,dp);
    }
}
class Solution {
public:

	int dp[105][105];
	/// Count Number of changes to be done
	/// to make substring of s from i to j 
	/// to palindrome
	int changes(int i , int j , string& s){
		int cnt = 0;
		while(i < j){
			cnt += (s[i++] != s[j--]);
		}
		return cnt;
	}

	int recur(int idx, int k, string &s){

		/// If Reached end of s and found partions to be done 0
		/// return 0 , otherwise return INT_MAX/any big number
		if(idx == s.size()){
			return (k == 0) ? 0 : 1e7;
		}

		/// Partitions to be done have completed , but
		/// we are not at the end of the string 
		/// return INT_MAX/any big number
		if(k == 0){
			return 1e7;
		}

		if (dp[idx][k] != -1){
			return dp[idx][k];
		}

		/// Partitioning the String
		int ans = INT_MAX;
		for (int i = idx ; i < s.size() ; i++){
			ans = min(ans , changes(idx , i , s) + recur(i + 1, k - 1, s));
		}
		return dp[idx][k] = ans;
	}

	int palindromePartition(string s, int k) {

		/// Edge Case
		if(k == s.size()){
			return 0;
		}
		memset(dp , -1 , sizeof(dp));
		return recur(0 , k , s);
	}

};
var palindromePartition = function(s, k) {
    const len = s.length;

    const cost = (i = 0, j = 0) => {
        let c = 0;
        while(i <= j) {
            if(s[i] != s[j]) c++;
            i++, j--;
        }
        return c;
    }

    const dp = Array.from({ length: len }, () => {
        return new Array(k + 1).fill(-1);
    })

    const splitHelper = (idx = 0, sl = k) => {
        if(sl < 0) return Infinity;
        if(idx == len) {
            if(sl == 0) return 0;
            return Infinity;
        }

        if(dp[idx][sl] != -1) return dp[idx][sl];

        let ans = Infinity;

        for(let i = idx; i < len; i++) {
            ans = Math.min(ans, splitHelper(i + 1, sl - 1) + cost(idx, i));
        }
        return dp[idx][sl] = ans;
    }

    return splitHelper();
};
Palindrome Partitioning III