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

Return the minimal number of characters that you need to change to divide the string.
 
Example 1:
Input: s = "abc", k = 2
Output: 1
Explanation: 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: You can split the string into "aa", "bb" and "c", all of them are palindrome.
Example 3:
Input: s = "leetcode", k = 8
Output: 0

 
Constraints:

1 <= k <= s.length <= 100.
s only contains lowercase English letters.

Difficulty: interview

Starter code:

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        

Solutions:
from functools import lru_cache
class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)
        if n == k:
            return 0
        @lru_cache(None)
        def cnt(left,right): # cost to make palindrome
            if left  >= right:
                return 0
            return cnt(left+1,right-1) + (s[left] != s[right])
        
        @lru_cache(None)
        def dp(length,partition):
            if partition == length:
                return 0
            if partition == 1:
                return cnt(0,length-1)
            return min(dp(prelength,partition-1) + cnt(prelength,length-1) for prelength in range(partition -1, length))

    
        return dp(n,k)


class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)
        visited = {}
        dic = {}
        def dfs(start, k):
            if (start, k) in dic:
                return dic[(start,k)]
            if k == 0:
                i = start
                j = n-1
                dic[(start, k)] = visited[(i,j)]
                return visited[(i,j)]
            count = float('inf')
            for i in range(start+1, n-k+1):
                count = min(count, visited[(start, i-1)]+dfs(i, k-1))
            
            dic[(start, k)] = count
            #print(dic)
            return count
        for j in range(n):
            for i in range(j, -1, -1):
                if i == j:
                    visited[(i,j)] = 0
                elif i == j-1:
                    if s[i] != s[j]:
                        visited[(i,j)] = 1
                    else:
                        visited[(i,j)] = 0
                else:
                    if s[i] == s[j]:
                        visited[(i,j)] = visited[(i+1,j-1)]
                    else:
                        visited[(i,j)] = visited[(i+1,j-1)]+1
        
        return dfs(0, k-1)


class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        # dp[i][k]: minimum cost to make s[:i] can be divided into k substring
        # xxxxxxxxxxxxxjxxxxxxi
        # dp[j-1][k-1]  s[j:i] 
        n = len(s)
        dp = [[math.inf for _ in range(k + 1)] for _ in range(n + 1)]
        dp[0][0] = 0
        
        def changes(start, end):
            cnt = 0
            while start < end:
                if s[start] != s[end]:
                    cnt += 1
                start += 1
                end -= 1
            return cnt
        
        for i in range(1, n + 1):
            for l in range(1, min(k, i) + 1):
                for j in range(l, i + 1):
                    dp[i][l] = min(dp[i][l], dp[j - 1][l - 1] + changes(j - 1, i - 1))
        
        return dp[n][k]


class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        # dp[i][j] is to partition s[:i] into j groups
        n = len(s)
        dp = [[float('inf')]*(k+1) for _ in range(n+1)]
        
        dp[0][0] = 0
        def cald(s):
            if len(s)==1:
                return 0
            else:
                lo, hi = 0, len(s)-1
                ans = 0
                while lo<hi:
                    if s[lo]!=s[hi]:
                        ans += 1
                    lo += 1
                    hi -= 1
                return ans

        for i in range(1,n+1): # to s[:i]
            for j in range(1,k+1):
                for h in range(j-1,i): # split into dp[h][] and s[h:i]
                    dp[i][j] = min(dp[i][j], dp[h][j-1]+ cald(s[h:i])  )
        return dp[n][k]
        


class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        # dp[i][j] is to partition s[:i] into j groups
        n = len(s)
        dp = [[float('inf')]*(k+1) for _ in range(n+1)]
        
        dp[0][0] = 0
        def cald(s):
            if len(s)==1:
                return 0
            else:
                lo, hi = 0, len(s)-1
                ans = 0
                while lo<hi:
                    if s[lo]!=s[hi]:
                        ans += 1
                    lo += 1
                    hi -= 1
                return ans
            
        for i in range(1,n+1): # to s[:i]
            for j in range(1,k+1):
                for h in range(j-1,i): # split into dp[h][] and s[h:i]
                    dp[i][j] = min(dp[i][j], dp[h][j-1]+ cald(s[h:i])  )
        return dp[n][k]
        


class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        l = len(s)
        def jbn(a):
            le = len(a)
            return sum(a[i] != a[le-1-i] for i in range(le //2))
        dp = [[0] * (l+1) for _ in range(k+1)]
        
        for j in range(1,l+1):
            dp[1][j] = jbn(s[:j])
        for i in range(2,k+1):
            for j in range(i+1,l+1):  # if j == i, dp[i][j] = 0
                # t = min(dp[i-1][i-1:j])
                # dp[i][j] = t + jbn(s[m:j])
                dp[i][j] = min(dp[i-1][m] + jbn(s[m:j]) for m in range(i-1,j))
        return dp[k][l]

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        def count_changes(_s):            
            m = len(_s) // 2
            return sum([int(c1 != c2) for c1, c2 in zip(_s[:m], _s[::-1][:m])])
            
        n = len(s)
        if n == k:
            return 0
        
        dp = [[float('inf')] * (n + 1) for _ in range(k + 1)]
        for i in range(1, n + 1):
            dp[1][i] = count_changes(s[:i])
        
        for _k in range(2, k + 1):
            for i in range(_k, n + 1):
                for j in range(_k - 1, i):
                    dp[_k][i] = min(dp[_k][i], dp[_k - 1][j] + count_changes(s[j:i]))
        
        return dp[k][n]


class Solution:
    def palindromePartition(self, s: str, key: int) -> int:
        
        @lru_cache(None)
        def repair(string: s) -> int:
            return sum([1 if string[i] != string[-1-i] else 0 for i in range(len(string)//2)])
        
        @lru_cache(None)
        def pp(start: int, end:int, k: int) -> int:
            # print(\"s:\", s, k)
            if k == len(s): return 0
            elif k == 1: return repair(s[start:end])
            changes = end-start-k
            for i in range(k-1, end-start):
                changes = min(pp(start, i, k-1) + repair(s[i:end]), changes)
            return changes
        
        return pp(0, len(s), key)

class Solution:
    def __init__(self):
        self.table = {}
        
    def palindromePartition(self, s: str, k: int) -> int:
            
        def distanceToPalindrome(subs):
            k = 0
            for i in range(int(len(subs)/2)):
                if subs[i] != subs[len(subs)-i-1]:
                    k += 1
            return k
                    
        if len(s) == 1:
            return 0
        
        if k == 1:
            return distanceToPalindrome(s)
        
        lens = len(s)
        if lens in self.table:
            if k in self.table[lens]:
                return self.table[lens][k]
                           
        out = len(s)          
        for i in range(1, len(s)):
            out = min(out, distanceToPalindrome(s[:i]) + self.palindromePartition(s[i:], k-1))
            
        if lens not in self.table:
            self.table[lens] = {}
        self.table[lens][k] = out
                                   
        return out

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        # dp[i][k]: min change number of devide s[:i] to k substrings
        
        dp = [[2 ** 30 for _ in range(k + 1)] for _ in range(len(s) + 1)]
        for p in range(k + 1):
            dp[0][p] = 0
        
        def minChange(s: str) -> int:
            i, j = 0, len(s) - 1
            cnt = 0
            while i < j:
                if s[i] != s[j]:
                    cnt += 1
                i += 1
                j -= 1
            return cnt

        for i in range(1, len(s) + 1):
            for p in range(1, min(i, k) + 1):
                for j in range(i, p-1, -1):
                    dp[i][p] = min(dp[i][p], dp[j-1][p-1] + minChange(s[j-1:i]))
        
        return dp[-1][-1]


class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        
        @lru_cache(None)
        def dfs(subs, k):
            if k == len(subs):
                return 0
            if k == 1:
                return sum(subs[i] != subs[-1-i] for i in range(len(subs)//2))
            res = float('inf')
            for i in range(1, len(subs) - k + 2):
                res = min(res, dfs(subs[:i], 1) + dfs(subs[i:], k - 1))
            return res
        return dfs(s, k)

from functools import lru_cache

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        N = len(s)
        
        @lru_cache(None)
        def numChanges(i, j):
            ct = 0
            while i < j:
                if s[i] != s[j]:
                    ct += 1
                i += 1
                j -= 1
            return ct
        
        @lru_cache(None)
        def dp(i, k):
            if i < k - 1:
                return inf
            if k == 1:
                return numChanges(0, i)
            return min(dp(j-1, k-1) + numChanges(j, i) for j in range(1, i+1))
        
        return dp(N-1, k)

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        def count_char(a):
            n = len(a)
            b = a[::-1]
            return sum(a[i] != b[i] for i in range(n)) // 2
        n = len(s)
        d = {}
        for i in range(n):
            for j in range(i, n):
                d[(i, j)] = count_char(s[i:j + 1])
        @lru_cache(None)
        def dfs(i, j, l):
            if l == j - i + 1:
                return 0
            if l == 1:
                return d[(i, j)]
            res = float('inf')
            for m in range(i, j - l + 2):
                res = min(res, d[(i, m)] + dfs(m + 1, j, l - 1))
            return res
        return dfs(0, len(s) - 1, k)

from functools import lru_cache
class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)
        if n == k:
            return 0
        @lru_cache(None)
        def cnt(left,right): # cost to make palindrome
            if left  >= right:
                return 0
            return cnt(left+1,right-1) + (s[left] != s[right])
        
        @lru_cache(None)
        def dp(length,partition):
            if partition == length:
                return 0
            if partition == 1:
                return cnt(0,length-1)
            return min(dp(prelength,partition-1) + cnt(prelength,length-1) for prelength in range(partition -1, length))

    
        return dp(n,k)


class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        self.memo = {}
        return self.dfs(s, k)
    
    def dfs(self, s, k):
        if (s, k) not in self.memo:
            res = float('inf')
            if len(s) == k:
                res = 0
            elif k == 1:
                res = sum(s[i] != s[-1-i] for i in range(len(s)//2))
            else:
                for i in range(1, len(s) - k + 2):
                    res = min(self.dfs(s[:i], 1) + self.dfs(s[i:], k - 1), res)
            self.memo[s, k] = res
        return self.memo[s, k]


class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        dp = defaultdict(int)
        def pali(i, j):
            diff = 0
            while i >= 0 and j < len(s):
                if s[i] != s[j]:
                    diff += 1
                dp[(i, j)] = diff
                i -= 1
                j += 1
        
        for i in range(len(s)):
            pali(i, i)
            pali(i, i+1)
        
        # memo = {}
        @lru_cache(maxsize=None)
        def recurse(idx, numCuts):
            if numCuts > k:
                return float('inf')
            
            if idx == len(s):
                if numCuts == k:
                    return 0
                return float('inf')
            
            curMin = float('inf')
            for i in range(idx, len(s)):
                curMin = min(dp[(idx, i)] + recurse(i+1, numCuts+1), curMin)
            return curMin
        
        return recurse(0, 0)

from functools import lru_cache
class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        @lru_cache(maxsize=None)
        def costs(i, j):
            if i>=j:
                return 0
            return costs(i+1,j-1)+(0 if s[i]==s[j] else 1)
        
        @lru_cache(maxsize=None)
        def dfs(j, k):
            if k==1:
                return costs(0,j)
            if k>j+1:
                return 0
            return min(dfs(i, k-1)+costs(i+1,j) for i in range(j))
        
        return dfs(len(s)-1, k)

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        
        
        n = len(s)
        s = '#' + s
        dp = [[float('inf')]*(k+1) for _ in range(n+1)]
        dp[0][0] = 0
        
        # def count(a, b):
        #     count = 0
        #     while a<b:
        #         if s[a] != s[b]:
        #             count +=1
        #         a +=1
        #         b -=1
        #     return count
        
        #挑战高难度count
        #dp[i][j]  change of characer betwee i and j
        count = [[0]*(n+1) for _ in range(n+1)]
        for lens in range(2, n+1):
            #i + lens -1 <= n+1
            for i in range(n-lens+2):
                j = i+ lens-1
                if s[i] == s[j]:
                    count[i][j] = count[i+1][j-1]
                else:
                    count[i][j] = count[i+1][j-1] + 1
        
                
    
            
        for i in range(1, n+1):
            for t in range(1, min(i+1, k+1)):
                for j in range(t, i+1):
                    dp[i][t] = min(dp[i][t], dp[j-1][t-1] + count[j][i])
                    
        return dp[n][k]

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        
        changes = [[0]*len(s) for _ in range(len(s))]
        
        for i in range(len(s)):
            for j in range(i,len(s)):
                start, end = i, j
                tmp = 0
                while start < end:
                    if s[start] != s[end]:
                        tmp += 1
                    start += 1
                    end -= 1
                changes[i][j] = tmp
        
        
        
        memo = [[float('inf')]*len(s) for _ in range(k)]
        
        for i in range(len(s)):
            memo[0][i] = changes[i][-1] 
        
        for i in range(1,k):
            for j in range(len(s)):
                for t in range(j+1, len(s)-i+1):
                    memo[i][j] = min(memo[i-1][t]+changes[j][t-1], memo[i][j])
        
        return memo[-1][0]
                    
                    
        


class Solution:
    def palindromePartition(self, s: str, K: int) -> int:
        n = len(s)
        # dp[i][k] means the minimal number of characters that I need to change to divide index 0 to index i from string s into k substrings
        dp = [[101 for k in range(K + 1)] for i in range(n)]
        num = [[0 for j in range(n)] for i in range(n)]
        
        for i in range(n):
            for j in range(i):
                num[j][i] = self.helper(s[j:i + 1])
        
        for i in range(n):
            dp[i][1] = num[0][i]

        for k in range(2, K + 1):
            for i in range(k - 1, n):
                for j in range(k - 2, i):
                    dp[i][k] = min(dp[i][k], dp[j][k - 1] + num[j + 1][i])
        return dp[n - 1][K]
    
    def helper(self, s):
        l, r = 0, len(s) - 1
        count = 0
        while l < r:
            if s[l] != s[r]:
                count += 1
            l += 1
            r -= 1
        return count

class Solution:
    def palindromePartition(self, s: str, k: int):
        prefix = [[0] * len(s) for _ in range(len(s))]
        for r in range(len(prefix)):
            for c in range(len(prefix[0])):
                if r < c:
                    prefix[r][c] = self.find_change(s, r, c)

        dp = [[0] * len(s) for _ in range(k)]
        dp[0] = prefix[0]
        for r in range(1, len(dp)):
            for c in range(len(dp[0])):
                if r < c:
                    tmp = float('inf')
                    for i in range(c):
                        tmp = min(tmp, dp[r-1][i] + prefix[i+1][c])
                    dp[r][c] = tmp
        return dp[-1][-1]

    def find_change(self, s, r, c):
        res = 0
        while r < c:
            if s[r] != s[c]:
                res += 1
            r += 1
            c -= 1
        return res

from functools import lru_cache

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        @lru_cache(None)
        def check(x):
            ans = 0
            for i in range(len(x) // 2):
                if x[i] != x[-1 - i]:
                    ans += 1
            return ans
        
        @lru_cache(None)
        def dfs(start, num):
            if num == 1:
                return check(s[start:])
            res = float('inf')
            for i in range(start + 1, len(s)):
                res = min(res, check(s[start:i]) + dfs(i, num - 1))
            return res
        
        return dfs(0, k)
                


from functools import lru_cache
class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)
        if n == k:
            return 0
        # a string of length n, the largest cost to make it  palindrome is n // 2
        @lru_cache(None)
        def cnt(left,right): # cost to make palindrome
            if left  >= right:
                return 0
            return cnt(left+1,right-1) + (s[left] != s[right])
        
        @lru_cache(None)
        def dp(length,partition):
            if partition == length:
                return 0
            if partition == 1:
                return cnt(0,length-1)
            res = float('inf')
            for prelength in range(partition - 1,length):
                res = min(res,dp(prelength,partition-1)+cnt(prelength,length-1))
            return res
    
        return dp(n,k)


class Solution:
    def palindromePartition(self, s: str, k: int):
        # preprocess
        cost = [[0] * len(s) for _ in range(len(s))]
        for i in range(len(s)-1, -1, -1):
            for j in range(i+1, len(s)):
                if s[i] == s[j]:
                    cost[i][j] = cost[i+1][j-1]
                else:
                    cost[i][j] = cost[i+1][j-1] + 1

        dp = [[float('inf')] * k for _ in range(len(s))]
        for i in range(len(s)):
            dp[i][0] = cost[0][i]
            for c in range(1, k):  # c means cut, so c = k - 1
                for j in range(i):
                    dp[i][c] = min(dp[i][c], dp[j][c-1] + cost[j+1][i])
        #print(dp)
        return dp[-1][-1]

class Solution:
    def palindromePartition(self, s: str, k: int):
        # preprocess
        cost = [[0] * len(s) for _ in range(len(s))]
        for i in range(len(s)-1, -1, -1):
            for j in range(i+1, len(s)):
                if s[i] == s[j]:
                    cost[i][j] = cost[i+1][j-1] 
                else:
                    cost[i][j] = cost[i+1][j-1] + 1

        dp = [[float('inf')] * (k+1) for _ in range(len(s))]
        for i in range(len(s)):
            dp[i][1] = cost[0][i]
            for m in range(2, k+1):
                for j in range(i):
                    dp[i][m] = min(dp[i][m], dp[j][m-1] + cost[j+1][i])
        #print(cost)
        #print(dp)
        return dp[-1][-1]

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        dp = {}
        def pali(i, j):
            diff = 0
            while i >= 0 and j < len(s):
                if s[i] != s[j]:
                    diff += 1
                dp[(i, j)] = diff
                i -= 1
                j += 1
        
        for i in range(len(s)):
            pali(i, i)
            pali(i, i+1)
            
        memo = {}
        def recurse(idx, numCuts):
            if numCuts == k and idx == len(s):
                return 0
            if numCuts == k or idx == len(s):
                return float('inf')
            
            if (idx, numCuts) in memo:
                return memo[(idx, numCuts)]
            curMin = float('inf')
            for j in range(idx, len(s)):
                curMin = min(dp[(idx, j)] + recurse(j+1, numCuts+1), curMin)
            memo[(idx, numCuts)] = curMin
            
            return curMin
        
        return recurse(0, 0)


class Solution:
    def palindromePartition(self, s: str, k: int):
        # preprocess
        cost = [[0] * len(s) for _ in range(len(s))]
        for i in range(len(s)-1, -1, -1):
            for j in range(i+1, len(s)):
                if s[i] == s[j]:
                    cost[i][j] = cost[i+1][j-1] 
                else:
                    cost[i][j] = cost[i+1][j-1] + 1

        dp = [[float('inf')] * k for _ in range(len(s))]
        for i in range(len(s)):
            dp[i][0] = cost[0][i]
            for m in range(1, k):
                for j in range(i):
                    dp[i][m] = min(dp[i][m], dp[j][m-1] + cost[j+1][i])
        #print(cost)
        #print(dp)
        return dp[-1][-1]

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)
        memo = {}
        
        def cost(s,i,j): #calculate the cost of transferring one substring into palindrome string
            r = 0
            while i < j:
                if s[i] != s[j]:
                    r += 1
                i += 1
                j -= 1
            return r
        
        def dfs(i, k):
            if (i, k) in memo: return memo[(i, k)] #case already in memo
            if n - i == k: #base case that each substring just have one character
                return 0
            if k == 1:    #base case that need to transfer whole substring into palidrome
                return cost(s, i, n - 1)
            res = float('inf')
            for j in range(i + 1, n - k + 2): # keep making next part of substring into palidrome
                res = min(res, dfs(j, k - 1) + cost(s,i, j - 1)) #compare different divisions to get the minimum cost
            memo[(i, k)] = res
            return res
        return dfs(0 , k)


class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)
        memo = {}
        
        def cost(s,i,j): #calculate the cost of transferring one substring into palindrome string
            r = 0
            while i < j:
                if s[i] != s[j]:
                    r += 1
                i += 1
                j -= 1
            return r
        
        def dfs(i, k):
            if (i, k) in memo: return memo[(i, k)] #case already in memo
            if n - i == k: #base case that each substring just have one character
                return 0
            if k == 1:    #base case that need to transfer whole substring into palidrome
                return cost(s, i, n - 1)
            res = float('inf')
            for j in range(i + 1, n - k + 2): # keep making next part of substring into palidrome
                res = min(res, dfs(j, k - 1) + cost(s,i, j - 1)) #compare different divisions to get the minimum cost
            memo[(i, k)] = res
            return res
        return dfs(0 , k)

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)
        memo = {}
        
        def cost(s,i,j): #calculate the cost of transferring one substring into palindrome string
            r = 0
            while i < j:
                if s[i] != s[j]:
                    r += 1
                i += 1
                j -= 1
            return r
        
        def dfs(i, k):
            if (i, k) in memo: return memo[(i, k)]
            if (n - i) == k: return 0
            if k == 1: return cost(s, i, n-1)
            res = n + 1 
            for j in range(i+1, n-k + 2):
                res = min(res, dfs(j, k-1) + cost(s, i, j-1))
            memo[(i, k)] = res 
            return res
            
        return dfs(0 , k)

'''
Dfs: either create new palindrome or expand

If expanding recurse down (num swaps and divides):
- With a swap you add 1
- Without, you don't add 

Edge of the pal has to be the next value

j-i = 0
j-i = 1
j-i = 2

Caching mechanism
'''
class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)
        memo = {}
        
        def cost(s,i,j): #calculate the cost of transferring one substring into palindrome string
            r = 0
            while i < j:
                if s[i] != s[j]:
                    r += 1
                i += 1
                j -= 1
            return r
        
        def dfs(i, k):
            if (i, k) in memo: return memo[(i, k)] #case already in memo
            if n - i == k: #base case that each substring just have one character
                return 0
            if k == 1:    #base case that need to transfer whole substring into palidrome
                return cost(s, i, n - 1)
            res = float('inf')
            for j in range(i + 1, n - k + 2): # keep making next part of substring into palidrome
                res = min(res, dfs(j, k - 1) + cost(s,i, j - 1)) #compare different divisions to get the minimum cost
            memo[(i, k)] = res
            return res
        return dfs(0 , k)
            
            
#             for j in range(i, self.length):
#                 t = self.dp.get((i,j+1))
#                 if not t:
#                     count = cost(i,j)
#                 else:
#                     count = t
                

#                 dfs(j+1,ch+count,nk-1) #  case where you split
             
#         dfs(0,0,k)

#         return self.r
                
            
            
            
            
            
# #         n = len(s)
# #         memo = {}
        
# #         def cost(s,i,j): #calculate the cost of transferring one substring into palindrome string
# #             r = 0
# #             while i < j:
# #                 if s[i] != s[j]:
# #                     r += 1
# #                 i += 1
# #                 j -= 1
# #             return r
        
# #         def dfs(i, k):
# #             if (i, k) in memo: return memo[(i, k)] #case already in memo
# #             if n - i == k: #base case that each substring just have one character
# #                 return 0
# #             if k == 1:    #base case that need to transfer whole substring into palidrome
# #                 return cost(s, i, n - 1)
# #             res = float('inf')
# #             for j in range(i + 1, n - k + 2): # keep making next part of substring into palidrome
# #                 res = min(res, dfs(j, k - 1) + cost(s,i, j - 1)) #compare different divisions to get the minimum cost
# #             memo[(i, k)] = res
# #             return res
# #         return dfs(0 , k)


class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        if len(s) <= k:
            return 0
        
        def num_change(w):#number need to change to become palindrome
            l,r=0,len(w)-1
            count=0
            while l<r:
                if w[l]!=w[r]:
                    count+=1
                l+=1
                r-=1
            return count
        
        def dp(i,k):
            if (i,k) not in memo:
                if k==1:
                    memo[i,k]=num_change(s[:i+1])
                else:
                    memo[i,k]=min(dp(j,k-1)+num_change(s[j+1:i+1]) for j in range(k-2,i))
            return memo[i,k]
        
        memo={}    
        n=len(s)
        return dp(n-1,k)

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        memo = dict()
        n = len(s)
        def find_cost(l, r):
            cost = 0
            while l < r:
                if s[l] != s[r]:
                    cost += 1
                l += 1
                r -= 1
            return cost
        
        def dp(i, k):
            if (i, k) in memo: return memo[(i, k)]
            if n-i == 1: return 0
            if k == 1: return find_cost(i, n-1)
            memo[(i, k)] = float('inf')
            for j in range(i+1, n-k+2):
                memo[(i, k)] = min(memo[(i, k)], find_cost(i, j-1)+dp(j, k-1))
            return memo[(i, k)]
        return dp(0, k)
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
#         n = len(s)
#         memo = dict()
#         cost_memo = dict()
#         def find_cost(l, r):
#             a, b = l, r
#             if (l, r) not in memo:
#                 cost = 0
#                 while l < r:
#                     cost += s[l] != s[r]
#                     l += 1
#                     r -= 1
#                 cost_memo[(a, b)] = cost
#             return cost_memo[(a, b)]
                
#         def top_down(i, k):
#             if n-i == 1:
#                 return 0
#             if k == 1:
#                 return find_cost(i, n-1)
#             if (i, k) not in memo:
#                 res = float('inf')
#                 for j in range(i+1, n-k+2):
#                     res = min(res, find_cost(i, j-1)+top_down(j, k-1))
#                 memo[(i, k)] = res
#             return memo[(i, k)]
#         return top_down(0, k)


class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)
        dp = [[float('inf') for _ in range(k)] for _ in range(n)]

           
        def getMinChange(i,j):
            count  = 0
            while i < j:
                if s[i] != s[j]:  count += 1
                i += 1
                j -= 1
            return count
        
        dic = collections.defaultdict(int) # dic[(i,j)] will store min change to make i:j a palindrome
        for i in range(n):
            for j in range(i,n):
                dic[(i,j)] = getMinChange(i,j)
                
        for i in range(n):
            for j in range(k):
                if j >= i: dp[i][j] = 0
                if j == 0: dp[i][j] = dic[(0,i)]
        z = k
        for i in range(n):
            for k in range(1,min(i+1,z)):
                for j in range(0,i): dp[i][k] = min(dp[i][k], dp[j][k-1] + dic[(j+1,i)])
        return dp[n-1][z-1]

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)
        memo = dict()
        cost_memo = dict()
        def find_cost(l, r):
            a, b = l, r
            if (l, r) not in memo:
                cost = 0
                while l < r:
                    cost += s[l] != s[r]
                    l += 1
                    r -= 1
                cost_memo[(a, b)] = cost
            return cost_memo[(a, b)]
                
        def top_down(i, k):
            if n-i == 1:
                return 0
            if k == 1:
                return find_cost(i, n-1)
            if (i, k) not in memo:
                res = float('inf')
                for j in range(i+1, n-k+2):
                    res = min(res, find_cost(i, j-1)+top_down(j, k-1))
                memo[(i, k)] = res
            return memo[(i, k)]
        return top_down(0, k)

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)
        self.cost = [[0 for _ in range(n)] for _ in range(n)]
        for l in range(2,n+1):
            i = 0
            while i+l-1<n:
                j = i+l-1
                self.cost[i][j] = self.cost[i+1][j-1] + (s[i]!=s[j])
                i += 1

        self.dp = [[n for _ in range(k+1)] for _ in range(n)]
        for i in range(n):
            self.dp[i][1] = self.cost[0][i]   # k=1就是一份，不分
            for K in range(2,k+1):
                for j in range(i):
                    self.dp[i][K] = min(self.dp[i][K], self.dp[j][K-1] + self.cost[j+1][i])
                    
        return self.dp[n-1][k]

class Solution:
    
    def palindromePartition(self, S: str, K: int) -> int:
        
        def palindrome_distance(li, ri):
            count = 0

            while li < ri:
                count += S[li] != S[ri]
                li += 1
                ri -= 1
                
            return count
        
        def dfs(i, k):
            if i == N or k == 0:
                return 0 if i == N and k == 0 else math.inf
            
            if (i, k) in memo:
                return memo[i, k]
            
            ans = math.inf
            
            for j in range(i, N):
                if (i, j) not in dist_memo:
                    dist_memo[i, j] = palindrome_distance(i, j)
                
                val = dist_memo[i, j] + dfs(j+1, k-1)
                ans = min(ans, val)
                
            memo[i, k] = ans
            return ans
                
        
        N = len(S)
        memo = {}
        dist_memo = {}
        ans = dfs(0, K)
        return ans


class Solution:
    def cost(self, i, j):
        if i + 1 >= j:
            return 0
        if i + 2 == j:
            return 0 if self.s[i] == self.s[j - 1] else 1
        
        try:
            return self.cost_cache[(i, j)]
        except KeyError:
            ret = self.cost(i + 1, j - 1) + (0 if self.s[i] == self.s[j - 1] else 1)
            self.cost_cache[(i, j)] = ret
            return ret
        
    def num_changes(self, i, kk):
        rem_len = len(self.s) - i
        if rem_len < kk:
            return self.MAX
        if rem_len == kk:
            return 0
        if kk == 1:
            return self.cost(i, len(self.s))
        
        try:
            return self.num_changes_cache[(i, kk)]
        except KeyError:
            ret = self.MAX
            for j in range(i + 1, len(self.s) - (kk - 1) + 1):
                ret = min(ret, self.cost(i, j) + self.num_changes(j, kk - 1))
            self.num_changes_cache[(i, kk)] = ret
            return ret
            
    def palindromePartition(self, s: str, k: int) -> int:
        self.s = s
        self.MAX = len(s)
        self.cost_cache = {}
        self.num_changes_cache = {}
        
        for l in range(3, len(s)):
            for i in range(len(s) - l + 1):
                j = i + l
                self.cost(i, j)
        for i in range(len(s) - 3, -1, -1):
            for kk in range(2, min(len(s) - i - 1, k - 1) + 1):
                self.num_changes(i, kk)
                
        return self.num_changes(0, k)
                
        


class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        self.cache = {}
        return self.dfs(s, k)
    
    def dfs(self, s, k):
        if (s, k) in self.cache:
            return self.cache[(s, k)]

        if k == 1:
            self.cache[(s, k)] = self.helper(s)
            return self.cache[(s, k)]
        
        n = len(s)
        ans = 100
        for i in range(n - k + 1):
            temp = self.helper(s[:i + 1])
            ans = min(ans, temp + self.dfs(s[i + 1:], k - 1))
        
        self.cache[(s, k)] = ans
        return ans
    
    def helper(self, s):
        l, r = 0, len(s) - 1
        count = 0
        while l < r:
            if s[l] != s[r]:
                count += 1
            l += 1
            r -= 1
        return count

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n=len(s)
        palindrome=[[0 for x in range(n)] for y in range(n)]
        for i in range(n-1):
            if s[i]!=s[i+1]:
                palindrome[i][i+1]=1
        for gap in range(2,n):
            for start in range(n-gap):
                end=start+gap
                if s[start]==s[end]:
                    palindrome[start][end]=palindrome[start+1][end-1]
                else:
                    palindrome[start][end]=palindrome[start+1][end-1]+1
        dp=[[2**31 for x in range(k+1)] for y in range(n+1)]
        dp[0][0]=0
        for i in range(1,n+1):
            for j in range(1,k+1):
                for l in range(i,0,-1):
                    dp[i][j]=min(dp[i][j],dp[l-1][j-1]+palindrome[l-1][i-1])
        return dp[n][k]
                    


class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        def change(s):
            if len(s) == 1:
                return 0
            i, j = 0, len(s) - 1
            count = 0
            while i < j:
                if s[i] != s[j]:
                    count += 1
                i +=1
                j -=1
            return count
        
        memo = [[-1] * (k+1) for _ in range(len(s))]
        
        def dfs(s, start, k):
            if memo[start][k] != -1: return memo[start][k]
            if k == 1: 
                memo[start][k] = change(s[start:])
                return memo[start][k]
            count = len(s) - start
            for i in range(start, len(s)-k+1):
                print(i, k)
                count = min(count, change(s[start:i+1]) + dfs(s, i+1, k-1))
            memo[start][k] = count
            return count
        
        return dfs(s, 0, k)

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        sLen = len(s)
        
        dp = {}
        
        def moveOnce(prei, i0, k0):
            if (prei, i0, k0) in dp:
                return dp[(prei, i0, k0)]
            if k0 == k:
                l = prei
                r = sLen -1
                subAns = 0
                while r > l:
                    if s[r] != s[l]:
                        subAns += 1
                    r -= 1
                    l += 1
                dp[(prei, i0, k0)] = subAns
                return subAns
            
            l = prei
            r = i0
            subAns = 0
            while r > l:
                if s[r] != s[l]:
                    subAns += 1
                r -= 1
                l += 1             
            if sLen - i0 - 1 <= k - k0:
                return subAns
            subAns = min(subAns + moveOnce(i0+1, i0+1,k0+1), moveOnce(prei, i0+1, k0))
            dp[(prei, i0, k0)] = subAns
            return subAns
        
        return moveOnce(0, 0, 1)
            
            


class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)
        dp = [[float('inf') for _ in range(k)] for _ in range(n)]

           
        def getMinChange(i,j):
            count  = 0
            while i < j:
                if s[i] != s[j]:  count += 1
                i += 1
                j -= 1
            return count
        
        dic = collections.defaultdict(int) # dic[(i,j)] will store min change to make i:j a palindrome
        for i in range(n):
            for j in range(i,n):
                dic[(i,j)] = getMinChange(i,j)
                
        for i in range(n):
            for j in range(k):
                if j >= i: dp[i][j] = 0
                if j == 0: dp[i][j] = dic[(0,i)]
        z = k
        for i in range(n):
            for k in range(1,z):
                for j in range(0,i): dp[i][k] = min(dp[i][k], dp[j][k-1] + dic[(j+1,i)])
        return dp[n-1][z-1]

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        # First, compute cost of each subdivision
        n = len(s)
        costs = [[0]*(n - i) for i in range(n)]
        for l in range(1, n):
            for start in range(n - l):
                old = costs[start + 1][l - 2] if l > 1 else 0
                costs[start][l] = old + (0 if s[start] == s[start + l] else 1)
        #print(costs)
        
        # Compute optimal splittings
        opt = [costs[i][-1] for i in range(n)]
        for ki in range(2, k + 1):
            new_opt = [0] * (n - ki + 1)
            for start in range(len(new_opt)):
                new_opt[start] = min(costs[start][l] + opt[start + l + 1] for l in range(n - start - ki + 1))
            opt = new_opt
        return opt[0]


class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        # dfs with memorization
        n = len(s)
        memo = dict()
        def cost(s, i, j):
            ans = 0
            while i < j:
                if s[i] != s[j]:
                    ans += 1
                i += 1
                j -= 1
            return ans
        
        def dfs(i, k):
            if (i, k) in memo:
                return memo[(i, k)]
            # the length of the substring is equal to k
            if n - i == k:
                return 0
            if k == 1:
                return cost(s, i, n-1)
            res = float('inf')
            for j in range(i, n-k+1):
                res = min(res, cost(s, i, j) + dfs(j+1, k-1))
            memo[(i, k)] = res
            return res
        return dfs(0, k)
                
            
            


class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        def min_change(s, i, j):
            a = 0
            while i < j:
                if s[i] != s[j]:
                    a+= 1
                
                i += 1
                j -= 1
            return a
        
        cost = [[0 for j in range(len(s) )] for i in range(len(s))]
        n = len(s)
        for l in range(2,n + 1):
            for i in range(n - l + 1):
                j = i + l - 1
                if s[i]!= s[j]:
                    cost[i][j] = cost[i + 1][j - 1] + 1 
                else:
                    cost[i][j] = cost[i + 1][j - 1]
             
        
        
        dp = [[float('inf') for j in range(n)] for i in range(k + 1)]
 
        #print(cost)
        for i in range(n):
            dp[1][i] = cost[0][i]
            for kk in range(2, k+ 1):
                for j in range( i):
                    dp[kk][i] = min(dp[kk][i]  , dp[kk - 1][j]  + cost[j + 1][i])
        
        return dp[-1][-1]
            


class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n=len(s)
        
        memo={}
        
        def cost(i,j):
            r = 0
            while i < j:
                if s[i] != s[j]:
                    r += 1
                i += 1
                j -= 1
            return r
        
        def divide(st,d):
            
            if (st,d) in memo:
                return memo[(st,d)]
            
            if d==n-st:
                return 0
            
            if d==1:
                return cost(st,n-1)
            
            ans=float('inf')
            
            for i in range(st+1,n-d+2):
                ans=min(ans,cost(st,i-1)+divide(i,d-1))
            
            memo[(st,d)]=ans
            
            return ans
        
        
        return divide(0,k)

class Solution1:
    def palindromePartition(self, s: str, k: int) -> int:
        dp = [[0] * len(s) for i in range(len(s))]
        
        n = len(s)
        
        def transferPalimCount(s) -> int:
            res = 0
            q = len(s) - 1
            p = 0
            
            while p < q:
                if s[p] != s[q]:
                    res += 1
                p += 1
                q -= 1
            return res

        for i in range(n):
            for j in range(i, n):
                dp[i][j] = transferPalimCount(s[i:j+1])
                
                

        def findMin(s, e, k, count, candidates):
            if k == 0:
                if s > e:
                    candidates.append(count)
                    return
                else:
                    count += dp[s][e]
                    candidates.append(count)
                    return
            
            # string is not able to split to too much parts
            if e-s+1 < k+1:
                return
        
            for i in range(s, e+1):
                findMin(i+1, e, k-1, count + dp[s][i], candidates)

        candidates = []
        findMin(0, n-1, k-1, 0, candidates)
        
        return min(candidates)

# https://leetcode.com/problems/palindrome-partitioning-iii/discuss/441427/Python3-Top-down-DFS-with-Memoization
class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)
        memo = {}
        def cost(s,i,j):
            r = 0
            while i < j:
                if s[i] != s[j]:
                    r += 1
                i += 1
                j -= 1
            return r
        
        def dfs(i, k):
            # case already in memo
            if (i, k) in memo: return memo[(i, k)]
            
            if n - i < k:
                return float('inf')
            
            # base case that each substring just have one character
            if n - i == k:
                return 0
            
            # base case that need to transfer whole substring into palidrome
            if k == 1:
                return cost(s, i, n - 1)

            res = float('inf')

            # keep making next part of substring into palidrome
            for j in range(i + 1, n):

                # compare different divisions to get the minimum cost
                res = min(res, dfs(j, k - 1) + cost(s, i, j - 1))
            memo[(i, k)] = res
            return res
        return dfs(0 , k)
        
        
        
                    


class Solution1:
    def palindromePartition(self, s: str, k: int) -> int:
        dp = [[0] * len(s) for i in range(len(s))]
        
        n = len(s)
        
        def transferPalimCount(s) -> int:
            res = 0
            q = len(s) - 1
            p = 0
            
            while p < q:
                if s[p] != s[q]:
                    res += 1
                p += 1
                q -= 1
            return res

        for i in range(n):
            for j in range(i, n):
                dp[i][j] = transferPalimCount(s[i:j+1])
                
                

        def findMin(s, e, k, count, candidates):
            if k == 0:
                if s > e:
                    candidates.append(count)
                    return
                else:
                    count += dp[s][e]
                    candidates.append(count)
                    return
            
            # string is not able to split to too much parts
            if e-s+1 < k+1:
                return
        
            for i in range(s, e+1):
                findMin(i+1, e, k-1, count + dp[s][i], candidates)

        candidates = []
        findMin(0, n-1, k-1, 0, candidates)
        
        return min(candidates)

# https://leetcode.com/problems/palindrome-partitioning-iii/discuss/441427/Python3-Top-down-DFS-with-Memoization
class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)
        memo = {}
        def cost(s,i,j):
            r = 0
            while i < j:
                if s[i] != s[j]:
                    r += 1
                i += 1
                j -= 1
            return r
        
        def dfs(i, k):
            # case already in memo
            if (i, k) in memo: return memo[(i, k)]
            
            # means not possible
            if n - i < k:
                return float('inf')
            
            # base case that each substring just have one character
            if n - i == k:
                return 0
            
            # base case that need to transfer whole substring into palidrome
            if k == 1:
                return cost(s, i, n - 1)

            res = float('inf')

            # keep making next part of substring into palidrome
            for j in range(i + 1, n):

                # compare different divisions to get the minimum cost
                res = min(res, dfs(j, k - 1) + cost(s, i, j - 1))
            memo[(i, k)] = res
            return res
        return dfs(0 , k)
        
        
        
                    


class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        
        def substring_palindrome(substring):
            l = 0
            r = len(substring) - 1
            ans = 0
            while l <= r:
                if substring[l] != substring[r]:
                    ans += 1
                l += 1
                r -= 1
            
            return ans
        
    
        n = len(s)  
        dp = {}
                    
        
        def backtrack(i, cuts):
            if (i, cuts) not in dp:
                # K is not cuts but subdivisions
                if cuts == 1:
                    dp[(i, cuts)] = substring_palindrome(s[:i+1])
                else:
                    ans = float('inf')
                    for end in range(cuts-2, i):
                        ans = min(ans, substring_palindrome(s[end+1:i+1]) + backtrack(end, cuts-1))
                    dp[(i, cuts)] = ans
                
                
                
            return dp[(i, cuts)]
        
        return backtrack(n-1, k)

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        def cost(st, i, j):
            res = 0
            while j > i:
                if st[i] != st[j]:
                    res += 1
                i += 1
                j -= 1
            return res
        memo = {}
        def dfs(l, r, k):
            if r-l < k:
                return float('inf')
            if r-l == k:
                return 0
            if k == 1:
                return cost(s, l, r-1)
            if (l, r, k) in memo:
                return memo[l, r, k]
            memo[l, r, k] = float('inf')
            for i in range(l+1, r):
                memo[l, r, k] = min(memo[l, r, k], dfs(l, i, k-1) + cost(s, i, r-1))
            return memo[l, r, k]
        return dfs(0, len(s), k)

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)
        if n == k:
            return 0
        
        # @lru_cache(None)
        def cost(s): #calculate the cost of transferring one substring into palindrome string
            r = 0
            i, j = 0, len(s) - 1
            while i < j:
                if s[i] != s[j]:
                    r += 1
                i += 1
                j -= 1
            return r
        
        @lru_cache(None)
        def dfs(s, k):
            if len(s) == k:
                return 0
            if k == 1:
                return cost(s)
            res = float('inf')
            for i in range(1, len(s)):
                res = min(res, cost(s[:i]) + dfs(s[i:], k-1))
            return res
        return dfs(s, k)

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        
        
        n = len(s)
        s = '#' + s
        dp = [[float('inf')]*(k+1) for _ in range(n+1)]
        dp[0][0] = 0
        
        def count(a, b):
            count = 0
            while a<b:
                if s[a] != s[b]:
                    count +=1
                a +=1
                b -=1
            return count
            
        for i in range(1, n+1):
            for t in range(1, min(i+1, k+1)):
                for j in range(t, i+1):
                    dp[i][t] = min(dp[i][t], dp[j-1][t-1] + count(j, i))
                    
        return dp[n][k]

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        
        @lru_cache(None)
        def dp(index, l):
            if l == 1:
                leftstr = s[index:]
                count = 0
                left, right = 0, len(leftstr)-1
                while(left < right):
                    if leftstr[left] != leftstr[right]:
                        count += 1
                    left += 1
                    right -= 1
                
                return count
            
            if index == len(s)-1:
                return 0
            
            minvalue  = float('inf')
            for i in range(index+1, len(s)):
                leftstr = s[index:i]
                count = 0
                left, right = 0, len(leftstr)-1
                while(left < right):
                    if leftstr[left] != leftstr[right]:
                        count += 1
                    left += 1
                    right -= 1             
                
                minvalue = min(minvalue, count + dp(i, l-1))
            
            return minvalue
        
        return dp(0, k)

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        def count(s):
            l=len(s)
            c=0
            for i in range(int(l//2)):
                if s[i]!=s[l-1-i]:
                    c+=1
            return c
        
        s='#'+s
        n=len(s)
        dp=[[float('inf')]*(k+1) for _ in range(n)]
        dp[0][0]=0
        for i in range(1,n):
            for j in range(1,k+1):
                for m in range(j,i+1):
                    dp[i][j]=min(dp[i][j],dp[m-1][j-1]+count(s[m:i+1]))
        
        return dp[-1][-1]

class Solution:
    def numChanges(self, s:str, start :int, end: int) -> int:
        num = 0
        while start < end:
            if not s[start] is s[end]:
                num +=1
            start += 1
            end -= 1
        return num
    
    
    def palindromePartition(self, s: str, k: int) -> int:
        cache = [[0 for _ in range(len(s))] for _ in range(k)]
        size = len(s)
        for j in range(size - 1, -1, -1):
            cache[0][j] = self.numChanges(s, j, size - 1)
        
        for i in range(1, k):
            for j in range(size - 1 - i, -1, -1):
                cache[i][j] = min([cache[i-1][k + 1] + self.numChanges(s,j,k) for k in range(j, size - i) ])
        return cache[k-1][0]
                
                


class Solution:
    def palindromePartition(self, s: str, K: int) -> int:
        len_s = len(s)
        if K >= len_s: return 0
        dp = [[float('inf')] * (K + 1) for _ in range(len_s + 1)]
        
        s = '0' + s
        dp[0][0] = 0
        for i in range(1, len_s + 1):
            for k in range(1, min(K + 1, i + 1)):
                for j in range(k, i + 1):
                    dp[i][k] = min(dp[i][k], dp[j-1][k-1] + self.helper(s, j, i))
        print(dp)
        return dp[-1][-1]
    
    def helper(self, sub_s, l_idx, r_idx):
        # 计算将sub_s转换为回文数，需要最少的操作字符数
        count = 0
        while l_idx < r_idx:
            if sub_s[l_idx] != sub_s[r_idx]:
                count += 1
            l_idx += 1
            r_idx -= 1
        return count

class Solution:
    def palindromePartition(self, s: str, K: int) -> int:
        len_s = len(s)
        if K >= len_s: return 0
        dp = [[float('inf')] * (K + 1) for _ in range(len_s + 1)]
        
        s = '0' + s
        dp[0][0] = 0
        for i in range(1, len_s + 1):
            for k in range(1, min(K + 1, i + 1)):
                for j in range(k, i + 1):
                    dp[i][k] = min(dp[i][k], dp[j-1][k-1] + self.helper(s, j, i))
        return dp[-1][-1]
    
    def helper(self, sub_s, l_idx, r_idx):
        # 计算将sub_s转换为回文数，需要最少的操作字符数
        count = 0
        while l_idx < r_idx:
            if sub_s[l_idx] != sub_s[r_idx]:
                count += 1
            l_idx += 1
            r_idx -= 1
        return count

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        def getCount(i: int, j: int):
            count = 0
            while i < j:
                if s[i] != s[j]:
                    count += 1
                i += 1
                j -= 1
            return count
        
        INT_MAX = 2147483647
        N = len(s)
        dp = [[INT_MAX for x in range(k)] for y in range(N)]
        
        for i in range(N):
            dp[i][0] = getCount(0, i)
            
        for i in range(1, k):
            for j in range(i, N):
                for x in range(i-1, j):
                    dp[j][i] = min(dp[j][i], dp[x][i-1]+getCount(x+1, j))
        return dp[N-1][k-1]

class Solution:
    def palindromePartition(self, s: str, K: int) -> int:
        len_s = len(s)
        if K >= len_s: return 0
        dp = [[float('inf')] * (K + 1) for _ in range(len_s + 1)]
        
        s = '0' + s
        dp[0][0] = 0
        for i in range(1, len_s + 1):
            for k in range(1, K + 1):
                for j in range(k, i + 1):
                    dp[i][k] = min(dp[i][k], dp[j-1][k-1] + self.helper(s, j, i))
        return dp[-1][-1]
    
    def helper(self, sub_s, l_idx, r_idx):
        # 计算将sub_s转换为回文数，需要最少的操作字符数
        count = 0
        while l_idx < r_idx:
            if sub_s[l_idx] != sub_s[r_idx]:
                count += 1
            l_idx += 1
            r_idx -= 1
        return count

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        # dp[i][j] min num of changes to divide j+1 subs in s[: i+1]
        # dp[i][j] = min([dp[i-m][j-1] + cost(i-m, j) for m in range(0, i)]
        n = len(s)
        dp = [[0 for j in range(k)] for i in range(n)]
        memo = {}
        # define the cost to make s[i: j+1] padindrome
        def cost(i, j):
            if memo.get((i, j)):
                return memo[(i, j)]
            c = 0
            while i < j:
                if s[i] != s[j]:
                    c += 1
                i += 1
                j -= 1
            memo[(i, j)] = c
            return c
        
        # we need to determine the maximum length of Palindrome centered at s[i]
        for i in range(n):
            for j in range(k):
                if j > i:
                    break
                if j == 0: 
                    dp[i][j] = cost(0, i)
                else:
                    dp[i][j] = min([dp[m][j-1] + cost(m+1, i) for m in range(i) if j-1<=m])
        return dp[n-1][k-1]
                    


def ch(a):
    l=len(a)
    c=0
    for i in range(l//2):
        c+=(a[i]!=a[l-i-1])
    return c
def f(s,ci,k,d):
    l=len(s)
    if k==0:
        if ci!=l:return math.inf
        return 0
    if ci==l:return math.inf
    if d[ci][k]!=-1:return d[ci][k]
    r=''
    a=math.inf
    for i in range(ci,l):
        r+=s[i]
        a= min(ch(s[ci:i+1])+f(s,i+1,k-1,d),a)   
    d[ci][k]=a
    return a
class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        l=len(s)
        d=[[-1for i in range(k+1)] for j in range(l)]
        return f(s,0,k,d)        

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        if not s:
            return
        self.memo = {}
        return self.helper(0, len(s), k, s)
    
    def helper(self, i, j, k, s):
        if (i, j, k) in self.memo:
            return self.memo[(i, j, k)]
        if len(s) <= k:
            return 0
        if k == 1:
            min_change = self.cal_palindrome(s[i:j])
            self.memo[(i, j, k)] = min_change
            return min_change
        
        min_change = float('inf')
        for split in range(i+1, j):
            left = self.cal_palindrome(s[i:split])
            right = self.helper(split, j, k-1, s)
            if left+right < min_change:
                min_change = left+right
        self.memo[(i, j, k)] = min_change
        return min_change
    
    def cal_palindrome(self, s):
        if len(s) == 1:
            return 0
        if len(s) % 2 == 0:
            c_right = len(s) // 2 
            c_left = c_right -1
        else:
            c_left = len(s) // 2 - 1
            c_right = len(s) // 2 + 1
        count = 0
        while c_left >= 0:
            if s[c_left] != s[c_right]:
                count += 1
            c_left -= 1
            c_right += 1
        return count