LeetCode 2911 - Minimum Changes to Make K Semi-palindromes

Difficulty: 🔴 Hard
Topics: Two Pointers, String, Dynamic Programming

Solution

Problem Understanding

The problem asks us to partition a given string s into k contiguous substrings and modify the characters minimally so that each substring becomes a semi-palindrome. A semi-palindrome is a string that can be divided into groups based on a repeating pattern length d (a divisor of the string length), where each group forms a palindrome. Essentially, we need to find a partitioning and minimal set of character changes so that each substring satisfies this semi-palindrome condition.

The input s is a lowercase English string with length between 2 and 200, and k is the number of partitions, which will always be less than or equal to half the length of s. The expected output is a single integer: the minimum number of letter changes required.

Important edge cases include strings that are already semi-palindromes, strings where each character is unique, and small strings where k equals 1 or the length of s is even or odd. These cases could trip up naive implementations, especially if they assume all strings can be split uniformly or ignore divisors correctly.

Approaches

The brute-force approach would enumerate all possible ways to partition s into k contiguous substrings. For each substring, we would try every possible divisor d to see how many character changes are needed to make it a semi-palindrome. While this guarantees correctness, it is extremely slow because the number of partitions grows combinatorially with string length and k, and checking semi-palindrome for each substring and divisor adds significant overhead.

The optimal approach relies on dynamic programming. We precompute the cost of converting every possible substring into a semi-palindrome. Using this precomputed cost table, we can define a DP array where dp[i][j] represents the minimum changes needed to partition the first i characters into j substrings. This allows us to compute the result efficiently by iterating over possible partition points and summing the minimal costs.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^k * n)	O(1)	Enumerates all partitions and all divisors, extremely slow
Optimal (DP + precompute costs)	O(n^2 * sqrt(n) * 26)	O(n^2)	Precompute semi-palindrome costs for all substrings, then DP for partitions

Algorithm Walkthrough

Precompute semi-palindrome costs for all substrings. Iterate over all substrings s[i:j+1]. For each substring, check every valid divisor d. For each divisor, divide the substring into d groups. For each group, compute how many character changes are needed to make it a palindrome by counting frequencies and subtracting the maximum frequency in the group. Store the minimum change over all divisors as the cost for that substring.
Initialize a DP array of size (n+1) x (k+1), where dp[i][j] represents the minimum number of changes needed to partition the first i characters into j substrings. Set dp[0][0] = 0 and all other entries to infinity.
Populate the DP array. For each i from 1 to n and for each j from 1 to k, consider every possible previous partition point p from 0 to i-1. Update dp[i][j] = min(dp[i][j], dp[p][j-1] + cost[p][i-1]).
Return the result. The value dp[n][k] is the minimum number of changes needed for the entire string partitioned into k semi-palindromes.

Why it works: By precomputing the minimal cost for every substring, we ensure that each potential partition is optimal for semi-palindrome conversion. The DP ensures that we explore all ways to partition the string into k substrings while accumulating the minimal total cost.

Python Solution

from collections import Counter
from math import isqrt

class Solution:
    def minimumChanges(self, s: str, k: int) -> int:
        n = len(s)
        
        # Precompute the minimal changes to make any substring s[i:j+1] a semi-palindrome
        cost = [[0] * n for _ in range(n)]
        
        for i in range(n):
            for j in range(i, n):
                substring = s[i:j+1]
                length = j - i + 1
                min_change = length  # max possible changes
                
                for d in range(1, length):
                    if length % d != 0:
                        continue
                    changes = 0
                    for g in range(d):
                        freq = Counter()
                        l, r = g, g
                        while l < length:
                            freq[substring[l]] += 1
                            l += d
                        group_len = (length - g + d - 1) // d
                        max_freq = max(freq.values())
                        changes += group_len - max_freq
                    min_change = min(min_change, changes)
                
                cost[i][j] = min_change
        
        # DP: dp[i][j] = min changes to partition first i characters into j substrings
        dp = [[float('inf')] * (k + 1) for _ in range(n + 1)]
        dp[0][0] = 0
        
        for i in range(1, n + 1):
            for j in range(1, min(k, i) + 1):
                for p in range(i):
                    dp[i][j] = min(dp[i][j], dp[p][j-1] + cost[p][i-1])
        
        return dp[n][k]

The code first precomputes the cost of turning every substring into a semi-palindrome using all valid divisors. It then uses dynamic programming to find the optimal partitioning that minimizes the total number of changes.

Go Solution

package main

import "math"

func minimumChanges(s string, k int) int {
    n := len(s)
    
    // Precompute cost to make substring s[i:j+1] a semi-palindrome
    cost := make([][]int, n)
    for i := range cost {
        cost[i] = make([]int, n)
    }
    
    for i := 0; i < n; i++ {
        for j := i; j < n; j++ {
            substr := s[i : j+1]
            length := j - i + 1
            minChange := length
            
            for d := 1; d < length; d++ {
                if length%d != 0 {
                    continue
                }
                changes := 0
                for g := 0; g < d; g++ {
                    freq := make(map[byte]int)
                    for l := g; l < length; l += d {
                        freq[substr[l]]++
                    }
                    maxFreq := 0
                    for _, v := range freq {
                        if v > maxFreq {
                            maxFreq = v
                        }
                    }
                    groupLen := (length - g + d - 1) / d
                    changes += groupLen - maxFreq
                }
                if changes < minChange {
                    minChange = changes
                }
            }
            
            cost[i][j] = minChange
        }
    }
    
    // DP
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, k+1)
        for j := range dp[i] {
            dp[i][j] = math.MaxInt
        }
    }
    dp[0][0] = 0
    
    for i := 1; i <= n; i++ {
        for j := 1; j <= k && j <= i; j++ {
            for p := 0; p < i; p++ {
                if dp[p][j-1]+cost[p][i-1] < dp[i][j] {
                    dp[i][j] = dp[p][j-1] + cost[p][i-1]
                }
            }
        }
    }
    
    return dp[n][k]
}

Go handles slices and maps instead of arrays and Counters. Overflow is not an issue here, but we explicitly initialize DP to math.MaxInt to represent infinity.

Worked Examples

Example 1: s = "abcac", k = 2

Compute costs:

Substring	Min changes
"a"	0
"ab"	1
"b"	0
"ca"	1
"cac"	0

DP table evolves:

dp[2][1] = 1 ("ab" → 1 change)
dp[5][2] = dp[2][1] + cost[2][4] = 1 + 0 = 1

Result = 1

Example 2: s = "abcdef", k = 2

Split as "abc" and "def", each needs 1 change → total 2

Example 3: s = "aabbaa", k = 3

Split as "aa", "bb", "aa" → all already semi-palindromes → total 0

Complexity Analysis

| Measure | Complexity | Explanation |

|---