Watch 3 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,484 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |