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)
Intuition
Two independent questions:
- What does one piece cost? For a substring of length
Land a proper divisordofL, the characters split intodsequences with stepd. Making a sequence a palindrome costs one change per mismatched mirror pair. The piece's cost is the minimum over its divisors. - How to split? Once every substring has a cost, choosing
kpieces 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
- For each
dfrom 1 ton / 2:- Fill
g[a][b](forb - aa multiple ofd) in order of increasingb - 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 ofdand at least2d, so thatdis a proper divisor: its cost with thisdisΣ g[i+r][j-d+1+r]forrin0..d-1. Keep the minimum incost[i][j].
- Fill
- Length-1 substrings keep cost infinity, since 1 has no proper divisor.
- Partition DP:
dp[j]is the best split ofs[:j]intoppieces. Start withp = 1,dp[j] = cost[0][j-1]. Thendp'[j] = min over i of dp[i] + cost[i][j-1], with2(p-1) <= i <= j-2, so every piece has length at least 2. - Return
dp[n]afterkpieces.
Complexity
- Time: O(n^2 log n + k * n^2). The
gtables totalΣ n^2 / (2d) = O(n^2 log n). FillingcosttakesΣ_L (n - L) * σ(L), around 10^6 atn = 200. The partition DP is O(k * n^2). - Space: O(n^2) for
costand onegtable reused acrossd
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 / 2keeps the problem feasible. d = 1is 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"withd = 3,"abab"withd = 2) - Prime lengths only have
d = 1, so such a piece must become an actual palindrome - In Java, the
gtable is shared across alldwithout clearing. Every read for a givendis either an entry already written for thatdor a diagonalg[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]import java.util.*;
/**
* 2911. Minimum Changes to Make K Semi-palindromes
* Time: O(n^2 log n + k * n^2)
* Space: O(n^2)
*/
class Solution {
public int minimumChanges(String s, int k) {
int n = s.length();
char[] c = s.toCharArray();
final int INF = Integer.MAX_VALUE / 2;
// cost[i][j] = fewest changes to make s[i..j] a semi-palindrome.
// Length-1 substrings have no valid divisor and stay INF.
int[][] cost = new int[n][n];
for (int[] row : cost) {
Arrays.fill(row, INF);
}
int[][] g = new int[n][n];
for (int d = 1; d <= n / 2; d++) {
// g[a][b] = changes to make c[a], c[a+d], ..., c[b] a palindrome
// (b - a a multiple of d). Peel the outer pair off the inner one.
// Every entry read below is written earlier for this same d.
for (int t = 1; t * d <= n - 1; t++) {
for (int a = 0; a + t * d < n; a++) {
int b = a + t * d;
int inner = t >= 2 ? g[a + d][b - d] : 0;
g[a][b] = inner + (c[a] != c[b] ? 1 : 0);
}
}
// 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 (int len = 2 * d; len <= n; len += d) {
for (int i = 0; i + len <= n; i++) {
int j = i + len - 1;
int sum = 0;
for (int r = 0; r < d; r++) {
sum += g[i + r][j - d + 1 + r];
}
cost[i][j] = Math.min(cost[i][j], sum);
}
}
}
// dp[j] = best way to split s[0..j) into p pieces, each of length >= 2.
int[] dp = new int[n + 1];
Arrays.fill(dp, INF);
for (int j = 2; j <= n; j++) {
dp[j] = cost[0][j - 1];
}
for (int p = 2; p <= k; p++) {
int[] next = new int[n + 1];
Arrays.fill(next, INF);
for (int j = 2 * p; j <= n; j++) {
// the last piece is s[i..j); the first p - 1 pieces need 2(p - 1) chars
for (int i = 2 * (p - 1); i <= j - 2; i++) {
next[j] = Math.min(next[j], dp[i] + cost[i][j - 1]);
}
}
dp = next;
}
return dp[n];
}
}