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: MEDIUM
Tags: String algorithms

Dynamic programming
Skill types: Dynamic programming

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):
			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
			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
				elif 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:
		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:
		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):
			for j in range(1, k + 1):
				for h in range(j - 1, 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):
				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:
			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 = [[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)


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)

		@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
		count = [[0] * (n + 1) for _ in range(n + 1)]
		for lens in range(2, 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 = [[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)


class Solution:

	def palindromePartition(self, s: str, k: int):
		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):
				for j in range(i):
					dp[i][c] = min(dp[i][c], dp[j][c - 1] + cost[j + 1][i])
		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) -> 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):
			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 = float('inf')
			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)


class Solution:

	def palindromePartition(self, s: str, k: int) -> int:
		if len(s) <= k:
			return 0

		def num_change(w):
			(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)


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)
		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]
			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)
		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)
		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:

		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)]
		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
			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)

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):
			if (i, k) in memo:
				return memo[i, k]
			if n - i < k:
				return float('inf')
			if n - i == k:
				return 0
			if k == 1:
				return cost(s, i, n - 1)
			res = float('inf')
			for j in range(i + 1, n):
				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:
				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:
		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):
		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:
		n = len(s)
		dp = [[0 for j in range(k)] for i in range(n)]
		memo = {}

		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
		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 = [[-1 for 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