We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Changes to Make K Semi-palindromes

Number: 2879

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given a string s and an integer k, partition s into k non-empty substrings. For each substring, you can change some letters so that the substring becomes a semi-palindrome. A string is considered a semi-palindrome if there exists a divisor d (1 ≤ d < length of the string and d divides the length) such that when the string is grouped by taking every d-th character (starting at positions 1 through d), every group forms a palindrome. The goal is to minimize the total number of letter changes necessary across all substrings.

Key Insights

  • For any substring (length L ≥ 2), iterate over every valid divisor d (1 ≤ d < L where L % d == 0).
  • For each divisor, split the substring into d groups by collecting characters at indices j, j+d, j+2d, ... for 0 ≤ j < d.
  • Compute the cost to turn each group into a palindrome (by counting mismatched pairs and needing one change per mismatched pair).
  • The minimal cost for the substring is the least cost over all valid divisors.
  • Use dynamic programming to partition the string into k substrings, where dp[i][t] represents the minimal cost to partition the first i characters into t segments.
  • Precompute the transformation cost for every possible substring, then use it in the DP transition.

Space and Time Complexity

Time Complexity: O(n^3) for precomputing every substring’s cost (n ≤ 200) plus O(n^2 * k) for the DP partitioning step, which is acceptable given the constraints. Space Complexity: O(n^2) for storing the cost for every substring, and O(n * k) for the DP table.

Solution

The solution works in two main stages:

  1. Precomputation: For every possible substring s[i...j], compute the minimum number of changes required to make it a semi-palindrome. For each valid divisor d of the substring’s length (excluding the length itself), split the substring into d groups. For each group, compute the number of letter changes required to turn it into a palindrome (by comparing symmetric characters). Take the minimum cost over all divisors.
  2. Dynamic Programming: Use a DP table dp[i][t] where dp[i][t] is the minimum cost to partition the first i characters into t segments. The recurrence relationship tries every possible previous partition point j such that the current segment s[j...i-1] (which is of length ≥2) can contribute its cost, and update dp[i][t+1] accordingly. The answer is dp[n][k] where n is the length of s.

Key data structures include a 2D cost array for substring transformation costs and a 2D DP table for partitioning.

Code Solutions

# Python solution with line-by-line comments

def min_changes_to_make_k_semi_palindromes(s, k):
    n = len(s)
    # Precompute cost[i][j] = minimum changes to make s[i:j+1] a semi-palindrome.
    cost = [[0] * n for _ in range(n)]
    
    # Helper function to compute cost for substring s[l:r+1]
    def compute_cost(l, r):
        L = r - l + 1
        # Initialize best_cost to a large number
        best_cost = float('inf')
        # Check all divisors d from 1 to L-1 that divide L
        for d in range(1, L):
            if L % d != 0:
                continue
            cur_cost = 0
            # For each group defined by d, compute cost to make it palindrome.
            for start in range(d):
                # Gather positions along the group
                group = []
                i = l + start
                while i <= r:
                    group.append(s[i])
                    i += d
                m = len(group)
                # Count mismatches in the group
                j = 0
                while j < m // 2:
                    if group[j] != group[m - 1 - j]:
                        cur_cost += 1
                    j += 1
            best_cost = min(best_cost, cur_cost)
        return best_cost if best_cost != float('inf') else 0

    # Fill in cost array for each substring with length at least 2
    for i in range(n):
        for j in range(i+1, n):
            cost[i][j] = compute_cost(i, j)
    
    # DP: dp[i][t] = minimal cost using first i characters partitioned into t segments.
    INF = float('inf')
    dp = [[INF] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 0

    # For each starting index i and number of segments used t, try to extend partition
    for i in range(n):
        for t in range(k):
            if dp[i][t] == INF:
                continue
            # Since each segment must be at least length 2, next j starts from i+2.
            for j in range(i+2, n+1):
                dp[j][t + 1] = min(dp[j][t + 1], dp[i][t] + cost[i][j - 1])
    
    return dp[n][k] if dp[n][k] != INF else -1

# Example usage:
print(min_changes_to_make_k_semi_palindromes("abcac", 2))  # Expected output: 1
print(min_changes_to_make_k_semi_palindromes("abcdef", 2)) # Expected output: 2
print(min_changes_to_make_k_semi_palindromes("aabbaa", 3)) # Expected output: 0
← Back to All Questions