2911. Minimum Changes to Make K Semi-palindromes

  • Two Pointers
  • String
  • Dynamic Programming
TIME
O(n^2 log n + k * n^2)
SPACE
O(n^2)
problem on leetcode ↗source on github ↗

Intuition

Two independent questions:

  1. What does one piece cost? For a substring of length L and a proper divisor d of L, the characters split into d sequences with step d. Making a sequence a palindrome costs one change per mismatched mirror pair. The piece's cost is the minimum over its divisors.
  2. How to split? Once every substring has a cost, choosing k pieces is a standard partition DP.

Computing piece costs directly is O(n^3 * divisors). That's too slow in Python at n = 200, and it repeats work: for a fixed step d, the sequence a, a+d, ..., b is a palindrome problem whose inner part is a+d, ..., b-d. That is the same recurrence as palindrome DP, just with stride d.

Approach

  1. For each d from 1 to n / 2:
    • Fill g[a][b] (for b - a a multiple of d) in order of increasing b - a: g[a][b] = g[a+d][b-d] + (s[a] != s[b]), with the inner term 0 when the sequence has 1 or 2 elements.
    • For every substring s[i..j] whose length is a multiple of d and at least 2d, so that d is a proper divisor: its cost with this d is Σ g[i+r][j-d+1+r] for r in 0..d-1. Keep the minimum in cost[i][j].
  2. Length-1 substrings keep cost infinity, since 1 has no proper divisor.
  3. Partition DP: dp[j] is the best split of s[:j] into p pieces. Start with p = 1, dp[j] = cost[0][j-1]. Then dp'[j] = min over i of dp[i] + cost[i][j-1], with 2(p-1) <= i <= j-2, so every piece has length at least 2.
  4. Return dp[n] after k pieces.

Complexity

  • Time: O(n^2 log n + k * n^2). The g tables total Σ n^2 / (2d) = O(n^2 log n). Filling cost takes Σ_L (n - L) * σ(L), around 10^6 at n = 200. The partition DP is O(k * n^2).
  • Space: O(n^2) for cost and one g table reused across d

Edge Cases

  • Single-character pieces are never semi-palindromes (the only divisor of 1 is 1 itself), so every piece needs length at least 2. k <= n / 2 keeps the problem feasible.
  • d = 1 is the plain palindrome check, and it applies to every length >= 2
  • A string can be a semi-palindrome with zero changes even though it isn't a palindrome ("abcabc" with d = 3, "abab" with d = 2)
  • Prime lengths only have d = 1, so such a piece must become an actual palindrome
  • In Java, the g table is shared across all d without clearing. Every read for a given d is either an entry already written for that d or a diagonal g[x][x], which is never written and stays 0.

Code

class Solution:
    def minimumChanges(self, s: str, k: int) -> int:
        """
        2911. Minimum Changes to Make K Semi-palindromes
        Time: O(n^2 log n + k * n^2)
        Space: O(n^2)
        """
        n = len(s)
        INF = float("inf")

        # cost[i][j] = fewest changes to make s[i..j] a semi-palindrome.
        # Length-1 substrings have no valid divisor and stay INF.
        cost = [[INF] * n for _ in range(n)]
        for d in range(1, n // 2 + 1):
            # g[a][b] = changes to make s[a], s[a+d], ..., s[b] a palindrome
            # (b - a a multiple of d). Peel the outer pair off the inner one.
            g = [[0] * n for _ in range(n)]
            for t in range(1, (n - 1) // d + 1):
                for a in range(n - t * d):
                    b = a + t * d
                    inner = g[a + d][b - d] if t >= 2 else 0
                    g[a][b] = inner + (s[a] != s[b])
            # Substrings whose length is a multiple of d, at least 2 * d, so
            # d is a proper divisor. Group r runs from i + r to j - d + 1 + r.
            for length in range(2 * d, n + 1, d):
                for i in range(n - length + 1):
                    j = i + length - 1
                    c = sum(g[i + r][j - d + 1 + r] for r in range(d))
                    if c < cost[i][j]:
                        cost[i][j] = c

        # dp[j] = best way to split s[:j] into p pieces, each of length >= 2.
        dp = [INF] * (n + 1)
        for j in range(2, n + 1):
            dp[j] = cost[0][j - 1]
        for p in range(2, k + 1):
            new = [INF] * (n + 1)
            for j in range(2 * p, n + 1):
                # the last piece is s[i:j]; the first p - 1 pieces need 2(p - 1) chars
                new[j] = min(dp[i] + cost[i][j - 1] for i in range(2 * (p - 1), j - 1))
            dp = new
        return dp[n]