Precomputed costs + partition DP
class Solution: def minimumChanges(self, s, k): n = len(s) def changes(part, d): # zip sees each mismatch twice groups = [part[r::d] for r in range(d)] return sum(sum(x != y for x, y in zip(g, g[::-1])) for g in groups) // 2 cost = [[0] * (n + 1) for _ in range(n + 1)] for start in range(n): for end in range(start + 2, n + 1): # 2+ chars each part = s[start:end] size = len(part) options = [changes(part, d) for d in range(1, size) if size % d == 0] cost[start][end] = min(options) best = [[float("inf")] * (k + 1) for _ in range(n + 1)] best[0][0] = 0 # best[end][parts]: s[:end] cut into parts for end in range(2, n + 1): for parts in range(1, k + 1): best[end][parts] = min( best[start][parts - 1] + cost[start][end] for start in range(end - 1)) return best[n][k]
The code from the episode, ready for LeetCode's Python 3 editor: paste it in and submit.
A ribbon repair shop finds two pieces that pass inspection without changing a patch. Folding jigs reveal how semi-palindromes work, and saved repair tags help compare complete partitions.
class Solution: def minimumChanges(self, s, k): n = len(s) infinity = float("inf") def cost(part): # Fewest changes that make `part` a semi-palindrome. best = infinity for d in range(1, len(part)): if len(part) % d != 0: continue # d must divide the length changes = 0 for r in range(d): group = part[r::d] # every d-th char from r for t in range(len(group) // 2): if group[t] != group[-1 - t]: changes += 1 best = min(best, changes) return best @lru_cache(maxsize=None) def split(start, parts): # Fewest changes to cut s[start:] into `parts` pieces. if parts == 1: return cost(s[start:]) if n - start >= 2 else infinity best = infinity # Leave at least 2 chars for each remaining piece. last_end = n - 2 * (parts - 1) for end in range(start + 2, last_end + 1): piece = cost(s[start:end]) best = min(best, piece + split(end, parts - 1)) return best return split(0, k)