2911. Minimum Changes to Make K Semi-palindromes
Difficulty: Hard
Topics: Principal, Two Pointers, String, Dynamic Programming, Weekly Contest 368
Given a string s and an integer k, partition s into k substrings1 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 palindromes2 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.
- Group 1 (positions
- 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.
- Group 1 (positions
Example 1:
- Input: s = "abcac", k = 2
- Output: 1
- Explanation: Divide
sinto"ab"and"cac"."cac"is already semi-palindrome. Change"ab"to"aa", it becomes semi-palindrome withd = 1.
Example 2:
- Input: s = "abcdef", k = 2
- Output: 2
- Explanation: Divide
sinto substrings"abc"and"def". Each needs one change to become semi-palindrome.
Example 3:
- Input: s = "aabbaa", k = 3
- Output: 0
- Explanation: Divide
sinto substrings"aa","bb"and"aa". All are already semi-palindromes.
Example 4:
- Input: s = "aa", k = 1
- Output: 0
Example 5:
- Input: s = "ab", k = 1
- Output: 1
Example 6:
- Input: s = "abcabc", k = 1
- Output: 0
Example 7:
- Input: s = "aaaa", k = 2
- Output: 0
Example 8:
- Input: s = "abc", k = 1
- Output: 1
Example 9:
- Input: s = "abcdef", k = 3
- Output: 3
Example 10:
- Input: s = "aabbcc", k = 3
- Output: 0
Constraints:
2 <= s.length <= 2001 <= k <= s.length / 2-
scontains only lowercase English letters.
Hint:
- Define
dp[i][j]as the minimum count of letter changes needed to split the suffix of stringsstarting froms[i]intojvalid parts. - We have
dp[i][j] = min(dp[x + 1][j - 1] + v[i][x]). Herev[i][x]is the minimum number of letter changes to change substrings[i..x]into semi-palindrome. -
v[i][j]can be calculated separately by brute-force. We can create a table ofv[i][j]independently to improve the complexity. Also note that semi-palindrome’s length is at least2.
Similar Questions:
Solution:
We precompute the minimum changes needed to turn every substring of length at least 2 into a semi-palindrome, then use dynamic programming to partition the whole string into exactly k valid semi-palindromic substrings with minimum total changes.
Approach
- Let
n = strlen(s). - Precompute
cost[l][r]: minimum letter changes to make substrings[l..r]a semi-palindrome.- Only consider substrings with length at least
2, because a semi-palindrome must have a valid divisord < length. - For each substring length
len, try every divisordfrom1tolen - 1. - For a fixed
d, split positions intodinterleaved groups using offsets0..d-1. - For each group, count mismatches between mirrored characters.
- Sum mismatches over all groups and take the minimum over all valid
d.
- Only consider substrings with length at least
- Define DP:
-
dp[i][p]= minimum changes needed to split suffixs[i..n-1]into exactlypsemi-palindromes. - Base case:
dp[n][0] = 0. - Transition: choose the end index
endof the first part, wheres[i..end]is a semi-palindrome, then adddp[end + 1][p - 1].
-
- Answer:
dp[0][k].
Let's implement this solution in PHP: 2911. Minimum Changes to Make K Semi-palindromes
<?php /** * @param String $s * @param Integer $k * @return Integer */ function minimumChanges(string $s, int $k): int { ... ... ... /** * go to ./solution.php */ } // Test cases echo minimumChanges("abcac", 2) . "\n"; // Output: 1 echo minimumChanges("abcdef", 2) . "\n"; // Output: 2 echo minimumChanges("aabbaa", 3) . "\n"; // Output: 0 echo minimumChanges("aa", 1) . "\n"; // Output: 0 echo minimumChanges("ab", 1) . "\n"; // Output: 1 echo minimumChanges("abcabc", 1) . "\n"; // Output: 0 echo minimumChanges("aaaa", 2) . "\n"; // Output: 0 echo minimumChanges("abc", 1) . "\n"; // Output: 1 echo minimumChanges("abcdef", 3) . "\n"; // Output: 3 echo minimumChanges("aabbcc", 3) . "\n"; // Output: 0 ?> Explanation
- A substring can only be semi-palindromic if its length is at least
2. - For a chosen divisor
d, the substring is divided intodgroups:- Group
offcontains positionsoff, off + d, off + 2d, .... - Each group must become a palindrome.
- Group
- To make a group a palindrome, we compare symmetric pairs inside that group and count unequal character pairs.
- The best
dfor a substring gives the minimum changes for that substring. - After all substring costs are known, the DP tries every possible partition into exactly
kparts. - Since
n <= 200, the brute-force cost precomputation is acceptable.
Complexity Analysis
- Let
n = |s|, and letτ(L)be the number of divisors ofL. - Cost precomputation:
- For each substring, we try divisors and process mirrored pairs.
- Worst-case safe bound:
O(n⁴). - Tighter bound:
O(n³ · τ(n))approximately.
- DP:
- States:
O(n · k). - Transitions: for each state, try possible ending positions:
O(k · n²).
- States:
- Overall time:
O(n⁴ + k · n²)safe upper bound, withn <= 200. - Space:
- Cost table:
O(n²). - DP table:
O(n · k). - Total:
O(n² + n · k).
- Cost table:
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:
-
Substring: A substring is a contiguous non-empty sequence of characters within a string. ↩
-
Palindrome: A palindrome is a string that reads the same forwards and backwards. ↩