IRAMIACADEMY Picture it. Then code it.
Problem 2911Hard

Minimum Changes to Make K Semi-palindromes

Two Pointers · String · Dynamic Programming

Precomputed costs + partition DP

solution.py
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]
Time O(n³ · D + k · n²)Space O(n² + k · n)

The code from the episode, ready for LeetCode's Python 3 editor: paste it in and submit.

The idea

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.

Check our socials
Another way: Memoized split, cost on demand
solution.py
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)
Time O(k · n³ · D)Space O(k · n)