Minimum Changes to Make K Semi-palindromes

Minimum Changes to Make K Semi-palindromes - Problem

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:

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.
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, ...; the second group includes characters at positions 2, 2+d, 2+2d, ... etc.
The string is considered a semi-palindrome if each of these groups forms a palindrome.

Example: Consider the string "abcabc" with length 6. Valid divisors are 1, 2, and 3. 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, so "abcabc" is a semi-palindrome.

Input & Output

Example 1 — Perfect Semi-palindromes

$ Input: s = "abcabc", k = 2

› Output: 0

💡 Note: Partition into "abc" and "abc". Both are already semi-palindromes with d=3: groups (a,a), (b,b), (c,c) are all palindromes. Cost = 0 + 0 = 0

Example 2 — Need Changes

$ Input: s = "abcdef", k = 2

› Output: 2

💡 Note: Best partition is "abc" | "def". For "abc" with d=1: need to change 'a'→'c' or 'c'→'a' (1 change). For "def" with d=1: need to change 'd'→'f' or 'f'→'d' (1 change). Total = 1 + 1 = 2

Example 3 — Single Characters

$ Input: s = "abc", k = 3

› Output: 0

💡 Note: Partition into "a", "b", "c". Single characters have no valid divisors, so cost is 0 for each. Total = 0 + 0 + 0 = 0

Constraints

1 ≤ s.length ≤ 200
1 ≤ k ≤ s.length
s consists only of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

String 'abcabc' needs to be split into k=2 parts

Partition

Find optimal way to split: 'abc' | 'abc'

Check

Each part is already a semi-palindrome, total cost = 0

Key Takeaway

🎯 Key Insight: Pre-compute all substring costs and use DP to find the optimal partitioning strategy

Asked in

G Google 12 M Microsoft 8 a Amazon 6

The key insight is to pre-compute the cost to convert any substring to a semi-palindrome, then use dynamic programming to find the optimal way to partition the string into k parts. Best approach uses 2D DP with memoization. Time: O(n³ + n²k), Space: O(n² + nk)

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with Memoization	O(n³ + n²k)	O(n² + nk)	Pre-compute costs and use 2D DP to find optimal partitioning
Brute Force Recursion	O(2^n × n³)	O(n)	Try all possible ways to partition the string into k parts recursively

Dynamic Programming with Memoization — Algorithm Steps

Pre-compute semi-palindrome costs for all substrings
Create DP table dp[i][j] = min cost for first i chars in j parts
Fill DP table using previously computed costs
Return dp[n][k] as the final answer

Visualization

Tap to expand

Step-by-Step Walkthrough

Pre-compute

Calculate costs for all substrings

DP Table

Fill dp[i][j] = min cost for i chars in j parts

Optimal

Return dp[n][k] as minimum cost

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int* getDivisors(int length, int* count) {
    int* divisors = malloc(length * sizeof(int));
    *count = 0;
    for (int d = 1; d < length; d++) {
        if (length % d == 0) {
            divisors[(*count)++] = d;
        }
    }
    return divisors;
}

int costToSemiPalindrome(const char* substr) {
    int len = strlen(substr);
    if (len <= 1) return 0;
    
    int divisorCount;
    int* divisors = getDivisors(len, &divisorCount);
    if (divisorCount == 0) {
        free(divisors);
        return INT_MAX;
    }
    
    int minCost = INT_MAX;
    for (int i = 0; i < divisorCount; i++) {
        int d = divisors[i];
        int cost = 0;
        
        char** groups = malloc(d * sizeof(char*));
        int* groupSizes = calloc(d, sizeof(int));
        
        for (int j = 0; j < d; j++) {
            groups[j] = malloc(len * sizeof(char));
        }
        
        for (int j = 0; j < len; j++) {
            int groupIdx = j % d;
            groups[groupIdx][groupSizes[groupIdx]++] = substr[j];
        }
        
        for (int j = 0; j < d; j++) {
            int left = 0, right = groupSizes[j] - 1;
            while (left < right) {
                if (groups[j][left] != groups[j][right]) {
                    cost++;
                }
                left++;
                right--;
            }
        }
        
        for (int j = 0; j < d; j++) {
            free(groups[j]);
        }
        free(groups);
        free(groupSizes);
        
        if (cost < minCost) {
            minCost = cost;
        }
    }
    
    free(divisors);
    return minCost == INT_MAX ? 0 : minCost;
}

int solution(char* s, int k) {
    int n = strlen(s);
    
    // Pre-compute costs
    int** costs = malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        costs[i] = malloc(n * sizeof(int));
        for (int j = i; j < n; j++) {
            char* substr = malloc((j - i + 2) * sizeof(char));
            strncpy(substr, s + i, j - i + 1);
            substr[j - i + 1] = '\0';
            costs[i][j] = costToSemiPalindrome(substr);
            free(substr);
        }
    }
    
    // DP table
    int** dp = malloc((n + 1) * sizeof(int*));
    for (int i = 0; i <= n; i++) {
        dp[i] = malloc((k + 1) * sizeof(int));
        for (int j = 0; j <= k; j++) {
            dp[i][j] = INT_MAX;
        }
    }
    dp[0][0] = 0;
    
    for (int i = 1; i <= n; i++) {
        int maxJ = (i < k) ? i : k;
        for (int j = 1; j <= maxJ; j++) {
            for (int prev = j - 1; prev < i; prev++) {
                if (dp[prev][j - 1] != INT_MAX) {
                    int newCost = dp[prev][j - 1] + costs[prev][i - 1];
                    if (newCost < dp[i][j]) {
                        dp[i][j] = newCost;
                    }
                }
            }
        }
    }
    
    int result = (dp[n][k] == INT_MAX) ? 0 : dp[n][k];
    
    // Cleanup
    for (int i = 0; i < n; i++) {
        free(costs[i]);
    }
    free(costs);
    
    for (int i = 0; i <= n; i++) {
        free(dp[i]);
    }
    free(dp);
    
    return result;
}

int main() {
    char s[1000];
    int k;
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    scanf("%d", &k);
    
    int result = solution(s, k);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³ + n²k)

O(n³) for pre-computing costs, O(n²k) for filling DP table

⚠ Quadratic Growth

Space Complexity

O(n² + nk)

O(n²) for cost matrix, O(nk) for DP table

⚠ Quadratic Space

12.0K Views

Medium Frequency

~35 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler