Minimum Changes to Make K Semi-palindromes - Video Solutions
2911. Minimum Changes to Make K Semi-palindromes | Weekly Leetcode 368
Minimum Changes to Make K Semi-palindromes - Video Solution
Watch 2 video solutions for Minimum Changes to Make K Semi-palindromes, a hard level problem involving Two Pointers, String, Dynamic Programming. This walkthrough by codingMohan has 1,565 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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.
- 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 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.
Approach Overview
Problem Overview: You are given a string s and an integer k. Split the string into k non-empty substrings such that every substring becomes a semi-palindrome. A semi-palindrome allows periodic symmetry: characters spaced by a fixed divisor mirror each other. The goal is to minimize the number of character changes required.
Approach 1: Dynamic Programming with Semi‑Palindrome Cost Precomputation (O(n^3) time, O(n^2) space)
The key challenge is evaluating how many edits are required to convert any substring s[i..j] into a semi‑palindrome. Precompute this cost for all substrings. For each length L, enumerate its divisors d. Treat indices with step d as independent sequences and check palindrome mismatches using a two pointers style comparison inside each group. Store the minimum change count in cost[i][j]. After preprocessing, apply dynamic programming where dp[i][p] represents the minimum cost to split the first i characters into p valid semi‑palindromes. Transition by iterating previous split points j and adding cost[j][i-1]. This approach systematically explores all partitions while reusing precomputed substring costs.
Approach 2: Greedy Partitioning with Preprocessing (O(n^3) time, O(n^2) space)
This strategy still relies on preprocessing substring costs but reduces DP state complexity by making locally optimal partition choices. First compute the edit cost for each substring using divisor grouping and mismatch counting over the string. Then iterate across the string and choose segment boundaries that minimize incremental change cost while ensuring exactly k segments remain feasible. The greedy step prioritizes substrings with the smallest conversion cost and adjusts boundaries when future segments would become impossible. While it often performs well in practice, correctness relies on careful feasibility checks for remaining characters.
Recommended for interviews: The dynamic programming approach with substring cost preprocessing is the expected solution. Brute force partitioning demonstrates understanding but quickly becomes exponential. Precomputing semi‑palindrome costs and combining it with DP shows strong problem decomposition and optimization skills, which interviewers typically look for in hard string DP problems.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Cost Preprocessing | O(n^3) | O(n^2) | General case. Guarantees optimal partitioning and is the most common interview solution. |
| Greedy with Preprocessed Costs | O(n^3) | O(n^2) | Useful when implementing faster heuristics in practice and when substring costs are already precomputed. |
| Brute Force Partition Enumeration | O(2^n * n) | O(n) | Conceptual baseline for understanding the partitioning search space. Not practical for large inputs. |