Skip to main content
Talentd

Minimum Changes to Make K Semi-palindromes - Solution & Explanation

HardTwo PointersStringDynamic Programming11 min read
Practice this problem

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:​

  1. Choose a positive divisor 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.
  2. For a given divisor 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.
  3. 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.

 

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.

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.

Approach 1: Dynamic Programming

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.

Code

CC++

C

C++

Complexity

Time Complexity: O(n^3) due to triple nested loop for each substring division
Space Complexity: O(n*k) for the dp array

Try this approach in the editor →

Approach 2: Greedy with Preprocessing

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.

Code

JavaPython

Java

Python

Complexity

Time Complexity: O(n^2 * k) simplified by preprocessing

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming

Time Complexity: O(n^3) due to triple nested loop for each substring division
Space Complexity: O(n*k) for the dp array

Greedy with Preprocessing

Time Complexity: O(n^2 * k) simplified by preprocessing

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with Cost PreprocessingO(n^3)O(n^2)General case. Guarantees optimal partitioning and is the most common interview solution.
Greedy with Preprocessed CostsO(n^3)O(n^2)Useful when implementing faster heuristics in practice and when substring costs are already precomputed.
Brute Force Partition EnumerationO(2^n * n)O(n)Conceptual baseline for understanding the partitioning search space. Not practical for large inputs.

Video Solution

2911. Minimum Changes to Make K Semi-palindromes | Weekly Leetcode 368 • codingMohan • 1,565 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Minimum Changes to Make K Semi-palindromes easy or hard?
Minimum Changes to Make K Semi-palindromes is classified as a Hard problem. It combines string processing, divisor-based pattern checks, and dynamic programming partitioning, which requires careful preprocessing and optimization to avoid exponential complexity.
Minimum Changes to Make K Semi-palindromes Python/Java solution
Python and Java implementations typically follow the same structure: precompute a cost matrix for all substrings, then run dynamic programming to split the string into k semi‑palindromes. The DP transition checks previous split points and accumulates the minimal edit cost.
How to solve Minimum Changes to Make K Semi-palindromes in O(n^3)?
Precompute a cost matrix where cost[i][j] represents the edits required to convert substring s[i..j] into a semi‑palindrome. For each substring length, test valid divisors and count mismatched mirrored characters within groups using two pointers. Then use DP where dp[i][p] stores the minimum edits needed to form p segments using the first i characters.
What is the best approach for Minimum Changes to Make K Semi-palindromes?
The most reliable approach uses dynamic programming with substring cost preprocessing. First compute the minimum edits required to convert every substring into a semi‑palindrome by checking valid divisors and counting mismatches. Then apply DP to partition the string into k segments while minimizing total cost. This runs in O(n^3) time and O(n^2) space.
Is Minimum Changes to Make K Semi-palindromes asked at Google/Amazon/Meta?
Problems involving string partitioning and dynamic programming frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that combine substring preprocessing with DP are common in senior-level interviews because they test both string manipulation and optimization skills.
What data structure is used in Minimum Changes to Make K Semi-palindromes?
The core solution relies on dynamic programming tables and a 2D matrix to store substring conversion costs. String indexing and two‑pointer comparisons are used to evaluate palindrome mismatches inside divisor-based character groups.
What is the time complexity of Minimum Changes to Make K Semi-palindromes?
The optimal solution typically runs in O(n^3) time. O(n^2) substrings are evaluated, and each substring may check multiple divisor groupings to compute semi‑palindrome costs. The dynamic programming partition step also iterates possible split points, resulting in cubic complexity overall with O(n^2) memory.

Ready to solve this problem?

Practice Minimum Changes to Make K Semi-palindromes with our built-in code editor and test cases.

Practice on FleetCode
Previous

Palindrome Partitioning III