LeetCode Solutions Blog

Minimum Changes to Make K Semi-palindromes

Difficulty: Hard

Problem Description

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.

Key Insights

A semi-palindrome can be formed by dividing the string into groups based on a positive divisor of its length.
Each group must form a palindrome for the substring to be considered a semi-palindrome.
The goal is to minimize the letter changes required to achieve k semi-palindromes.

Space and Time Complexity

Time Complexity: O(n^2 * k)
Space Complexity: O(n)

Solution

To solve this problem, we can use dynamic programming. We define a DP array where dp[i][j] represents the minimum changes needed to create j semi-palindromes from the first i characters of the string. We will also need a helper function to calculate the minimum changes required to make a substring semi-palindromic based on possible divisors.

Precompute the minimum changes for every possible substring of the string.
Use a nested loop to fill the DP table:
- The outer loop iterates over the length of the substring.
- The inner loop counts the number of semi-palindromes that can be formed.
Update the DP array based on the minimum changes computed for each partition.

Code Solutions

def minChanges(s: str, k: int) -> int:
    n = len(s)
    # Precompute the minimum changes required to make each substring a semi-palindrome
    changes = [[0] * n for _ in range(n)]
    
    for length in range(1, n + 1):  # length of the substring
        for start in range(n - length + 1):
            end = start + length - 1
            # Calculate the number of changes needed to make s[start:end+1] a semi-palindrome
            changes[start][end] = calculate_changes(s[start:end + 1])
    
    # DP array where dp[i][j] is the minimum changes to make the first i chars into j semi-palindromes
    dp = [[float('inf')] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 0  # 0 characters into 0 semi-palindromes requires 0 changes

    for i in range(1, n + 1):
        for j in range(1, min(i, k) + 1):
            for p in range(i):  # p is the end of the last partition
                dp[i][j] = min(dp[i][j], dp[p][j - 1] + changes[p][i - 1])

    return dp[n][k]

def calculate_changes(substring: str) -> int:
    # Function to calculate the minimum changes required to make the substring a semi-palindrome
    length = len(substring)
    total_changes = 0
    for d in range(1, length):
        if length % d == 0:  # Check if d is a valid divisor
            groups = [[] for _ in range(d)]
            for i in range(length):
                groups[i % d].append(substring[i])
            # For each group, count changes to make it a palindrome
            changes = 0
            for group in groups:
                changes += count_changes_to_palindrome(group)
            total_changes = min(total_changes, changes)
    return total_changes

def count_changes_to_palindrome(group: list) -> int:
    # Count the changes needed to make a group a palindrome
    left, right = 0, len(group) - 1
    changes = 0
    while left < right:
        if group[left] != group[right]:
            changes += 1
        left += 1
        right -= 1
    return changes