Problem statement

A string of length len is a semi-palindrome if there is an integer d with 1 <= d < len and len % d == 0 such that, when the characters are grouped by their index modulo d, every group read in order is a palindrome. For example "adbgad" is one with d = 2: the groups "aba" (indices 0, 2, 4) and "dgd" (indices 1, 3, 5) are palindromes. A single character is never a semi-palindrome, since no valid d exists.

Given a string s and an integer k, split s into exactly k non-empty contiguous substrings and then change as few characters as possible so that every substring is a semi-palindrome.

Return the minimum number of character changes needed.

Example 1

Input: s = "abcac", k = 2
Output: 1
Explanation: Split into "ab" and "cac". "cac" is already a palindrome (d = 1); "ab" needs one change to become "aa".

Example 2

Input: s = "abcdef", k = 2
Output: 2
Explanation: Split into "abc" and "def"; each needs one change to become a palindrome.

Example 3

Input: s = "aabbaa", k = 3
Output: 0
Explanation: "aa", "bb" and "aa" are already semi-palindromes.

Constraints

• 2 <= s.length <= 200
• 1 <= k <= s.length / 2
• s consists of lowercase English letters

Hints for Minimum Changes to Make K Semi-palindromes

1. Hint 1

   First answer a smaller question: what does it cost to turn one substring s[i..j] into a semi-palindrome?

2. Hint 2

   For a fixed divisor d of the length, each residue group is fixed independently: compare its characters pairwise from both ends and count mismatches. Take the minimum over all valid d.

3. Hint 3

   With every substring's cost precomputed, the split is a standard partition DP: dp[p][e] = cheapest way to cut the first e characters into p pieces, each piece at least 2 long.

How to solve Minimum Changes to Make K Semi-palindromes

The problem separates into two layers: a per-substring cost (best divisor d, mismatched mirror pairs inside each residue group) and a partition DP that chooses where to cut.

Approach

1. For every substring s[i..j] with length L ≥ 2, and every d with 1 ≤ d < L and L % d == 0: for each residue r < d, its group has m = L / d characters s[i + r + t·d]; count positions t < m / 2 whose character differs from its mirror s[i + r + (m - 1 - t)·d]. The sum over residues is the cost for d; cost[i][j] is the minimum over d.
2. Let dp[p][e] be the fewest changes to split s[0..e-1] into p semi-palindromes, with dp[0][0] = 0 and everything else infinite.
3. dp[p][e] = min over b ≤ e - 2 of dp[p-1][b] + cost[b][e-1].
4. Return dp[k][n].

Why it works

Within a residue group, making it a palindrome only constrains mirrored pairs, and each mismatched pair needs exactly one change (set one character to the other), so the count of mismatched pairs is exact. Different residue groups share no characters, so their costs add. The substrings of a split are independent, so the partition DP over precomputed costs is exact.

Complexity

• Time — O(n^2 · σ(n) + k · n^2), where σ(n) is the sum of divisors — about O(n^3) in practice
• Space — O(n^2)

Pitfalls

• d must be strictly less than the length, so a length-1 piece is impossible — keep every piece at least 2 long.
• d = 1 is allowed and means the substring itself must be a palindrome.
• Mirror within the group, not within the substring: the partner of the t-th group member is the (m - 1 - t)-th member.

Reference solution

Python

def minimumChanges(s: str, k: int) -> int:
    n = len(s)
    INF = float('inf')
    cost = [[INF] * n for _ in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            L = j - i + 1
            best = INF
            for d in range(1, L):
                if L % d:
                    continue
                m = L // d
                ch = 0
                for r in range(d):
                    for t in range(m // 2):
                        if s[i + r + t * d] != s[i + r + (m - 1 - t) * d]:
                            ch += 1
                best = min(best, ch)
            cost[i][j] = best
    dp = [INF] * (n + 1)
    dp[0] = 0
    for _ in range(k):
        nd = [INF] * (n + 1)
        for e in range(2, n + 1):
            for b in range(e - 1):
                if dp[b] < INF:
                    v = dp[b] + cost[b][e - 1]
                    if v < nd[e]:
                        nd[e] = v
        dp = nd
    return dp[n]

Java

public static int minimumChanges(String s, int k) {
    int n = s.length();
    final int INF = 1 << 29;
    int[][] cost = new int[n][n];
    for (int[] row : cost) Arrays.fill(row, INF);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int L = j - i + 1;
            for (int d = 1; d < L; d++) {
                if (L % d != 0) continue;
                int m = L / d, ch = 0;
                for (int r = 0; r < d; r++) {
                    for (int t = 0; t < m / 2; t++) {
                        if (s.charAt(i + r + t * d) != s.charAt(i + r + (m - 1 - t) * d)) ch++;
                    }
                }
                cost[i][j] = Math.min(cost[i][j], ch);
            }
        }
    }
    int[] dp = new int[n + 1];
    Arrays.fill(dp, INF);
    dp[0] = 0;
    for (int p = 0; p < k; p++) {
        int[] nd = new int[n + 1];
        Arrays.fill(nd, INF);
        for (int e = 2; e <= n; e++) {
            for (int b = 0; b + 2 <= e; b++) {
                if (dp[b] < INF) nd[e] = Math.min(nd[e], dp[b] + cost[b][e - 1]);
            }
        }
        dp = nd;
    }
    return dp[n];
}

C++

int minimumChanges(string s, int k) {
    int n = s.size();
    const int INF = 1 << 29;
    vector<vector<int>> cost(n, vector<int>(n, INF));
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int L = j - i + 1;
            for (int d = 1; d < L; d++) {
                if (L % d != 0) continue;
                int m = L / d, ch = 0;
                for (int r = 0; r < d; r++) {
                    for (int t = 0; t < m / 2; t++) {
                        if (s[i + r + t * d] != s[i + r + (m - 1 - t) * d]) ch++;
                    }
                }
                cost[i][j] = min(cost[i][j], ch);
            }
        }
    }
    vector<int> dp(n + 1, INF);
    dp[0] = 0;
    for (int p = 0; p < k; p++) {
        vector<int> nd(n + 1, INF);
        for (int e = 2; e <= n; e++) {
            for (int b = 0; b + 2 <= e; b++) {
                if (dp[b] < INF) nd[e] = min(nd[e], dp[b] + cost[b][e - 1]);
            }
        }
        dp = nd;
    }
    return dp[n];
}

JavaScript

var minimumChanges = function(s, k) {
    var n = s.length, INF = 1 << 29;
    var cost = [];
    for (var i = 0; i < n; i++) cost.push(new Array(n).fill(INF));
    for (var i = 0; i < n; i++) {
        for (var j = i + 1; j < n; j++) {
            var L = j - i + 1;
            for (var d = 1; d < L; d++) {
                if (L % d !== 0) continue;
                var m = L / d, ch = 0;
                for (var r = 0; r < d; r++) {
                    for (var t = 0; t < (m >> 1); t++) {
                        if (s[i + r + t * d] !== s[i + r + (m - 1 - t) * d]) ch++;
                    }
                }
                if (ch < cost[i][j]) cost[i][j] = ch;
            }
        }
    }
    var dp = new Array(n + 1).fill(INF);
    dp[0] = 0;
    for (var p = 0; p < k; p++) {
        var nd = new Array(n + 1).fill(INF);
        for (var e = 2; e <= n; e++) {
            for (var b = 0; b + 2 <= e; b++) {
                if (dp[b] < INF && dp[b] + cost[b][e - 1] < nd[e]) nd[e] = dp[b] + cost[b][e - 1];
            }
        }
        dp = nd;
    }
    return dp[n];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Longest Chunked Palindrome Decomposition Hard
• Closest Subsequence Sum Hard
• Maximum Score of a Good Subarray Hard
• Kth Smallest Product of Two Sorted Arrays Hard
• Subsequence With the Minimum Score Hard
• Last Substring in Lexicographical Order Hard