Minimum Changes to Make K Semi-palindromes
HardUpdated: Aug 2, 2025
Practice on:
Problem
Given a string s and an integer k, partition s into k substrings such that the letter changes needed to make each substring a semi-palindrome are minimized.
Return the minimum number of letter changes required .
A semi-palindrome is a special type of string that can be divided into palindromes based on a repeating pattern. To check if a string is a semi-palindrome:
- Choose a positive divisor
dof the string's length.dcan range from1up to, but not including, the string's length. For a string of length1, it does not have a valid divisor as per this definition, since the only divisor is its length, which is not allowed. - For a given divisor
d, divide the string into groups where each group contains characters from the string that follow a repeating pattern of lengthd. Specifically, the first group consists of characters at positions1,1 + d,1 + 2d, and so on; the second group includes characters at positions2,2 + d,2 + 2d, etc. - The string is considered a semi-palindrome if each of these groups forms a palindrome.
Consider the string "abcabc":
- The length of
"abcabc"is6. Valid divisors are1,2, and3. - For
d = 1: The entire string"abcabc"forms one group. Not a palindrome. - For
d = 2: - Group 1 (positions
1, 3, 5):"acb" - Group 2 (positions
2, 4, 6):"bac" - Neither group forms a palindrome.
- For
d = 3:
- For
- Group 1 (positions
1, 4):"aa" - Group 2 (positions
2, 5):"bb" - Group 3 (positions
3, 6):"cc" - All groups form palindromes. Therefore,
"abcabc"is a semi-palindrome.
Examples
Example 1
Input: s = "abcac", k = 2
Output: 1
Explanation: Divide `s` into `"ab"` and `"cac"`. `"cac"` is already semi-
palindrome. Change `"ab"` to `"aa"`, it becomes semi-palindrome with `d = 1`.
Example 2
Input: s = "abcdef", k = 2
Output: 2
Explanation: Divide `s` into substrings `"abc"` and `"def"`. Each needs
one change to become semi-palindrome.
Example 3
Input: s = "aabbaa", k = 3
Output: 0
Explanation: Divide `s` into substrings `"aa"`, `"bb"` and `"aa"`. All are
already semi-palindromes.
Constraints
2 <= s.length <= 2001 <= k <= s.length / 2scontains only lowercase English letters.
Solution
Method 1 – Dynamic Programming + Semi-palindrome Cost Precomputation
Intuition
To minimize changes, we need to split the string into k substrings and, for each, find the minimum changes to make it a semi-palindrome. Precompute the cost for every substring to become a semi-palindrome, then use dynamic programming to find the optimal partitioning.
Approach
- For every substring, precompute the minimum changes needed to make it a semi-palindrome:
- For each possible divisor d, group characters and count changes to make each group a palindrome.
- Take the minimum over all valid divisors.
- Use DP:
dp[i][j]= min changes to partition first i characters into j semi-palindromes.- For each partition, try all possible previous cuts and update dp.
- Return
dp[n][k]where n is the length of s.
Code
C++
class Solution {
public:
int minChanges(string s, int k) {
int n = s.size();
vector<vector<int>> cost(n, vector<int>(n, 0));
for (int l = 0; l < n; ++l) {
for (int r = l; r < n; ++r) {
int len = r - l + 1, minCost = INT_MAX;
for (int d = 1; d < len; ++d) {
if (len % d != 0) continue;
int cur = 0;
for (int i = 0; i < d; ++i) {
int left = i, right = len - d + i;
while (left < right) {
if (s[l + left] != s[l + right]) cur++;
left += d;
right -= d;
}
}
minCost = min(minCost, cur);
}
cost[l][r] = (len == 1 ? 0 : minCost);
}
}
vector<vector<int>> dp(n + 1, vector<int>(k + 1, INT_MAX));
dp[0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= k; ++j) {
for (int p = j - 1; p < i; ++p) {
if (dp[p][j - 1] != INT_MAX && cost[p][i - 1] != INT_MAX)
dp[i][j] = min(dp[i][j], dp[p][j - 1] + cost[p][i - 1]);
}
}
}
return dp[n][k];
}
};
Go
func minChanges(s string, k int) int {
n := len(s)
cost := make([][]int, n)
for i := range cost {
cost[i] = make([]int, n)
}
for l := 0; l < n; l++ {
for r := l; r < n; r++ {
len := r - l + 1
minCost := 1 << 30
for d := 1; d < len; d++ {
if len%d != 0 {
continue
}
cur := 0
for i := 0; i < d; i++ {
left, right := i, len-d+i
for left < right {
if s[l+left] != s[l+right] {
cur++
}
left += d
right -= d
}
}
if cur < minCost {
minCost = cur
}
}
if len == 1 {
cost[l][r] = 0
} else {
cost[l][r] = minCost
}
}
}
dp := make([][]int, n+1)
for i := range dp {
dp[i] = make([]int, k+1)
for j := range dp[i] {
dp[i][j] = 1 << 30
}
}
dp[0][0] = 0
for i := 1; i <= n; i++ {
for j := 1; j <= k; j++ {
for p := j - 1; p < i; p++ {
if dp[p][j-1] < 1<<30 && cost[p][i-1] < 1<<30 {
if dp[p][j-1]+cost[p][i-1] < dp[i][j] {
dp[i][j] = dp[p][j-1] + cost[p][i-1]
}
}
}
}
}
return dp[n][k]
}
Java
class Solution {
public int minChanges(String s, int k) {
int n = s.length();
int[][] cost = new int[n][n];
for (int l = 0; l < n; ++l) {
for (int r = l; r < n; ++r) {
int len = r - l + 1, minCost = Integer.MAX_VALUE;
for (int d = 1; d < len; ++d) {
if (len % d != 0) continue;
int cur = 0;
for (int i = 0; i < d; ++i) {
int left = i, right = len - d + i;
while (left < right) {
if (s.charAt(l + left) != s.charAt(l + right)) cur++;
left += d;
right -= d;
}
}
minCost = Math.min(minCost, cur);
}
cost[l][r] = (len == 1 ? 0 : minCost);
}
}
int[][] dp = new int[n + 1][k + 1];
for (int[] arr : dp) Arrays.fill(arr, Integer.MAX_VALUE);
dp[0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= k; ++j) {
for (int p = j - 1; p < i; ++p) {
if (dp[p][j - 1] != Integer.MAX_VALUE && cost[p][i - 1] != Integer.MAX_VALUE)
dp[i][j] = Math.min(dp[i][j], dp[p][j - 1] + cost[p][i - 1]);
}
}
}
return dp[n][k];
}
}
Kotlin
class Solution {
fun minChanges(s: String, k: Int): Int {
val n = s.length
val cost = Array(n) { IntArray(n) }
for (l in 0 until n) {
for (r in l until n) {
val len = r - l + 1
var minCost = Int.MAX_VALUE
for (d in 1 until len) {
if (len % d != 0) continue
var cur = 0
for (i in 0 until d) {
var left = i
var right = len - d + i
while (left < right) {
if (s[l + left] != s[l + right]) cur++
left += d
right -= d
}
}
minCost = minOf(minCost, cur)
}
cost[l][r] = if (len == 1) 0 else minCost
}
}
val dp = Array(n + 1) { IntArray(k + 1) { Int.MAX_VALUE } }
dp[0][0] = 0
for (i in 1..n) {
for (j in 1..k) {
for (p in j - 1 until i) {
if (dp[p][j - 1] != Int.MAX_VALUE && cost[p][i - 1] != Int.MAX_VALUE)
dp[i][j] = minOf(dp[i][j], dp[p][j - 1] + cost[p][i - 1])
}
}
}
return dp[n][k]
}
}
Python
def min_changes(s: str, k: int) -> int:
n = len(s)
cost = [[0] * n for _ in range(n)]
for l in range(n):
for r in range(l, n):
length = r - l + 1
min_cost = float('inf')
for d in range(1, length):
if length % d != 0:
continue
cur = 0
for i in range(d):
left, right = i, length - d + i
while left < right:
if s[l + left] != s[l + right]:
cur += 1
left += d
right -= d
min_cost = min(min_cost, cur)
cost[l][r] = 0 if length == 1 else min_cost
dp = [[float('inf')] * (k + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(1, n + 1):
for j in range(1, k + 1):
for p in range(j - 1, i):
if dp[p][j - 1] != float('inf') and cost[p][i - 1] != float('inf'):
dp[i][j] = min(dp[i][j], dp[p][j - 1] + cost[p][i - 1])
return dp[n][k]
Rust
impl Solution {
pub fn min_changes(s: String, k: i32) -> i32 {
let n = s.len();
let s = s.as_bytes();
let mut cost = vec![vec![0; n]; n];
for l in 0..n {
for r in l..n {
let len = r - l + 1;
let mut min_cost = i32::MAX;
for d in 1..len {
if len % d != 0 { continue; }
let mut cur = 0;
for i in 0..d {
let mut left = i;
let mut right = len - d + i;
while left < right {
if s[l + left] != s[l + right] { cur += 1; }
left += d;
right -= d;
}
}
min_cost = min_cost.min(cur);
}
cost[l][r] = if len == 1 { 0 } else { min_cost };
}
}
let mut dp = vec![vec![i32::MAX; (k + 1) as usize]; n + 1];
dp[0][0] = 0;
for i in 1..=n {
for j in 1..=k as usize {
for p in j - 1..i {
if dp[p][j - 1] != i32::MAX && cost[p][i - 1] != i32::MAX {
dp[i][j] = dp[i][j].min(dp[p][j - 1] + cost[p][i - 1]);
}
}
}
}
dp[n][k as usize]
}
}
TypeScript
class Solution {
minChanges(s: string, k: number): number {
const n = s.length;
const cost: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
for (let l = 0; l < n; l++) {
for (let r = l; r < n; r++) {
const len = r - l + 1;
let minCost = Infinity;
for (let d = 1; d < len; d++) {
if (len % d !== 0) continue;
let cur = 0;
for (let i = 0; i < d; i++) {
let left = i, right = len - d + i;
while (left < right) {
if (s[l + left] !== s[l + right]) cur++;
left += d;
right -= d;
}
}
minCost = Math.min(minCost, cur);
}
cost[l][r] = len === 1 ? 0 : minCost;
}
}
const dp: number[][] = Array.from({ length: n + 1 }, () => Array(k + 1).fill(Infinity));
dp[0][0] = 0;
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= k; j++) {
for (let p = j - 1; p < i; p++) {
if (dp[p][j - 1] !== Infinity && cost[p][i - 1] !== Infinity) {
dp[i][j] = Math.min(dp[i][j], dp[p][j - 1] + cost[p][i - 1]);
}
}
}
}
return dp[n][k];
}
}
Complexity
- ⏰ Time complexity:
O(n^3), due to precomputing costs for all substrings and divisors, and DP partitioning. - 🧺 Space complexity:
O(n^2), for cost and DP tables.