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:
d of the string's length. d can range from 1 up to, but not including, the string's length. For a string of length 1, it does not have a valid divisor as per this definition, since the only divisor is its length, which is not allowed.d, divide the string into groups where each group contains characters from the string that follow a repeating pattern of length d. Specifically, the first group consists of characters at positions 1, 1 + d, 1 + 2d, and so on; the second group includes characters at positions 2, 2 + d, 2 + 2d, etc.Consider the string "abcabc":
"abcabc" is 6. Valid divisors are 1, 2, and 3.d = 1: The entire string "abcabc" forms one group. Not a palindrome.d = 2:
1, 3, 5): "acb"2, 4, 6): "bac"d = 3:
1, 4): "aa"2, 5): "bb"3, 6): "cc""abcabc" is a semi-palindrome.
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 / 2s contains only lowercase English letters.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.
Use dynamic programming to solve this problem by calculating the minimum changes needed to convert each substring into a semi-palindrome. This involves breaking the problem into subproblems where each subproblem calculates the minimum changes required for a semi-palindrome for every substring division at different indices.
The C solution defines a helper function palindrome_changes to calculate the number of changes needed to make a substring a palindrome. The main function minChangesToMakeKPalindromes uses dynamic programming to fill out dp[i][j] which represents the minimum changes needed to create j semi-palindromes from the first i characters. It uses a double loop to ensure that every division is considered, and previous calculated results are reused to optimize the solution.
Time Complexity: O(n^3) due to triple nested loop for each substring division
Space Complexity: O(n*k) for the dp array
This approach involves a preprocessing step to approximate the number of changes needed to convert each possible substring into a semi-palindrome. Using a greedy strategy, we then try to partition the string into k substrings while minimizing changes for each partition step.
The Java solution uses a greedy approach complemented by a preprocessing step that calculates changes required for each potential substring to become a semi-palindrome. The greedy part tries various partitions and adjusts for the minimum necessary changes using preprocessed values to decide the optimal split points.
Time Complexity: O(n^2 * k) simplified by preprocessing
| Approach | Complexity |
|---|---|
| Dynamic Programming | Time Complexity: O(n^3) due to triple nested loop for each substring division |
| Greedy with Preprocessing | Time Complexity: O(n^2 * k) simplified by preprocessing |
| 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. |
2911. Minimum Changes to Make K Semi-palindromes | Weekly Leetcode 368 • codingMohan • 1,484 views views
Watch 2 more video solutions →Practice Minimum Changes to Make K Semi-palindromes with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor