1
class Solution:
2
    def palindromePartition(self, s: str, t: int) -> int:
3
        n = len(s)
4

5
        @lru_cache(None)
6
        def is_palin(
7
            s,
8
        ):  # This function returns min no of chars to change to make s as a palindrome
9
            cnt = 0
10
            for c1, c2 in zip(s, s[::-1]):
11
                if c1 != c2:
12
                    cnt += 1
13
            if len(s) % 2 == 0:
14
                return cnt // 2
15
            return (cnt + 1) // 2
16

17
        @lru_cache(None)
18
        def dp(i, j, k):  # We analyse string s[i:j+1] with k divisions left
19
            if j == n:
20
                return 0 if k == 0 else sys.maxsize
21
            if k == 0:
22
                return sys.maxsize
23
            ans = sys.maxsize
24
            cnt = is_palin(s[i : j + 1])
25
            # terminate here
26
            ans = min(ans, dp(j + 1, j + 1, k - 1) + cnt)
27
            # dont terminate
28
            ans = min(ans, dp(i, j + 1, k))
29
            return ans
30

31
        return dp(0, 0, t)