The string is considered a semi-palindrome if each of these groups forms a palindrome.

Consider the string "abcabc":

The length of "abcabc" is 6. Valid divisors are 1, 2, and 3.
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:
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 <= 200
1 <= k <= s.length / 2
s contains 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

[{"language":"C++","code":"class Solution {\npublic:\n    int minChanges(string s, int k) {\n        int n = s.size();\n        vector<vector<int>> cost(n, vector<int>(n, 0));\n        for (int l = 0; l < n; ++l) {\n            for (int r = l; r < n; ++r) {\n                int len = r - l + 1, minCost = INT_MAX;\n                for (int d = 1; d < len; ++d) {\n                    if (len % d != 0) continue;\n                    int cur = 0;\n                    for (int i = 0; i < d; ++i) {\n                        int left = i, right = len - d + i;\n                        while (left < right) {\n                            if (s[l + left] != s[l + right]) cur++;\n                            left += d;\n                            right -= d;\n                        }\n                    }\n                    minCost = min(minCost, cur);\n                }\n                cost[l][r] = (len == 1 ? 0 : minCost);\n            }\n        }\n        vector<vector<int>> dp(n + 1, vector<int>(k + 1, INT_MAX));\n        dp[0][0] = 0;\n        for (int i = 1; i <= n; ++i) {\n            for (int j = 1; j <= k; ++j) {\n                for (int p = j - 1;

Related Tags