Minimum Changes to Make K Semi-palindromes

• Define a recursive function solve(index, parts_left) that computes the minimum cost to partition the suffix s[index...] into parts_left semi-palindromes.
• Base Case 1: If parts_left is 0, return 0 if index is at the end of the string (n), otherwise return infinity (an invalid partition).
• Base Case 2: If index is at or beyond the end of the string but parts_left > 0, return infinity.
• Recursive Step: Iterate through all possible split points i for the current substring s[index...i]. The loop for i must ensure that the remaining string s[i+1...] is long enough for the remaining parts_left - 1 partitions.
• For each substring s[index...i], calculate its cost to become a semi-palindrome. This involves checking all its valid divisors and finding the minimum number of character changes required.
• Make a recursive call solve(i + 1, parts_left - 1) to find the cost for the rest of the string.
• The total cost for this split is the sum of the current substring's cost and the result of the recursive call.
• Return the minimum total cost found among all possible split points i.
• The initial call is solve(0, k).

The core of this approach is a recursive function, let's call it solve(index, parts_left), which aims to find the minimum cost to partition the suffix of the string starting at index into parts_left semi-palindromes.

Algorithm Steps:

1. Base Cases: The recursion terminates when either all partitions are used (parts_left == 0) or the end of the string is reached (index >= n). If parts_left == 0 and index == n, a valid partition has been found, and the cost is 0. In all other terminal cases, the partition is invalid, represented by a very large cost (infinity).
2. Recursive Logic: The function iterates through all possible end points i for the current substring, which starts at index. For each potential substring s[index...i], it first calculates the minimum changes needed to make it a semi-palindrome. This helper calculation itself involves iterating through all valid divisors of the substring's length and finding the minimum changes.
3. After getting the cost for s[index...i], the function makes a recursive call solve(i + 1, parts_left - 1) to find the optimal cost for the remaining part of the string. The sum of these two costs represents the total cost for this specific partition choice.
4. The function maintains a variable to track the minimum total cost found across all choices for the split point i and returns this minimum.

The initial call to solve the entire problem is solve(0, k).

1class Solution {2    public int minimumChanges(String s, int k) {3        return solve(s, 0, k);4    }5 6    private int calculateCost(String sub) {7        int len = sub.length();8        if (len < 2) return Integer.MAX_VALUE / 2;9 10        List<Integer> divs = new ArrayList<>();11        for (int d = 1; d < len; d++) {12            if (len % d == 0) divs.add(d);13        }14        if (divs.isEmpty()) return Integer.MAX_VALUE / 2;15 16        int minChanges = len;17        for (int d : divs) {18            int currentChanges = 0;19            for (int rem = 0; rem < d; rem++) {20                int groupLen = len / d;21                for (int p = 0; p < groupLen / 2; p++) {22                    if (sub.charAt(rem + p * d) != sub.charAt(rem + (groupLen - 1 - p) * d)) {23                        currentChanges++;24                    }25                }26            }27            minChanges = Math.min(minChanges, currentChanges);28        }29        return minChanges;30    }31 32    private int solve(String s, int index, int parts_left) {33        int n = s.length();34        if (parts_left == 0) {35            return index == n ? 0 : Integer.MAX_VALUE / 2;36        }37        // Each of the remaining 'parts_left' partitions must have length at least 2.38        if (n - index < 2 * parts_left) {39            return Integer.MAX_VALUE / 2;40        }41 42        int minTotalCost = Integer.MAX_VALUE / 2;43        // The current partition s[index...i] must leave enough characters for the rest.44        for (int i = index; i <= n - 2 * parts_left; i++) {45            String sub = s.substring(index, i + 1);46            int currentCost = calculateCost(sub);47            if (currentCost < Integer.MAX_VALUE / 2) {48                int remainingCost = solve(s, i + 1, parts_left - 1);49                if (remainingCost < Integer.MAX_VALUE / 2) {50                    minTotalCost = Math.min(minTotalCost, currentCost + remainingCost);51                }52            }53        }54        return minTotalCost;55    }56}

This recursive solution can be optimized with memoization, which effectively transforms it into the dynamic programming approach described next. Without memoization, it re-explores the same (index, parts_left) states repeatedly.

• Phase 1: Precomputation
  • Precompute divisors for all numbers from 1 to n. This can be done in O(n * sqrt(n)) time.
  • Create a 2D array min_costs[i][j] to store the minimum changes needed to make the substring s[i...j] a semi-palindrome.
  • Iterate through all substrings s[i...j] of length L >= 2.
  • For each substring, iterate through its precomputed divisors d.
  • For each d, calculate the total changes required by summing the changes for each of the d character groups to become palindromes.
  • Store the minimum changes over all d in min_costs[i][j].
• Phase 2: Dynamic Programming
  • Create a 2D DP table dp[i][p], where dp[i][p] is the minimum cost to partition the prefix s[0...i-1] into p parts.
  • Initialize dp[0][0] = 0 and all other entries to infinity.
  • Iterate p from 1 to k (number of partitions).
  • Iterate i from 2*p to n (length of the prefix).
  • Iterate j from 2*(p-1) to i-2 (the split point).
  • Apply the transition: dp[i][p] = min(dp[i][p], dp[j][p-1] + min_costs[j][i-1]).
• The final answer is dp[n][k].

This efficient approach is divided into two main parts: precomputing the costs for all substrings and then using dynamic programming to find the optimal partition.

1. Precomputation of Substring Costs

We first calculate the minimum changes required to make any substring s[i...j] a semi-palindrome and store it in a table min_costs[i][j]. This avoids costly recalculations during the DP phase.

• Divisor Precomputation: To quickly find divisors for any substring length, we can pre-generate lists of divisors for all numbers from 1 to n.
• Cost Calculation: We iterate through all possible substrings s[i...j]. For each substring of length L, we iterate through its valid divisors d (1 <= d < L). For a given d, the substring is conceptually split into d groups. The cost for this d is the sum of changes to make each group a palindrome. The cost for s[i...j], i.e., min_costs[i][j], is the minimum of these costs over all possible d.

1// Precomputing divisors for efficiency2List<Integer>[] divisors = new List[n + 1];3for (int i = 1; i <= n; i++) {4    divisors[i] = new ArrayList<>();5    for (int j = 1; j * j <= i; j++) {6        if (i % j == 0) {7            if (j < i) divisors[i].add(j);8            if (i / j != j && i / j < i) divisors[i].add(i / j);9        }10    }11}12 13// Precomputing costs for all substrings14int[][] min_costs = new int[n][n];15for (int i = 0; i < n; i++) {16    for (int j = i + 1; j < n; j++) {17        int len = j - i + 1;18        int current_min = len; // A safe upper bound19        for (int d : divisors[len]) {20            int changes = 0;21            for (int rem = 0; rem < d; rem++) {22                int group_len = len / d;23                for (int p = 0; p < group_len / 2; p++) {24                    if (s.charAt(i + rem + p * d) != s.charAt(i + rem + (group_len - 1 - p) * d)) {25                        changes++;26                    }27                }28            }29            current_min = Math.min(current_min, changes);30        }31        min_costs[i][j] = current_min;32    }33}

2. Dynamic Programming

With the min_costs table ready, we can solve the main problem.

• DP State: dp[i][p] = minimum cost to partition prefix s[0...i-1] (length i) into p semi-palindromes.
• DP Table: An (n+1) x (k+1) table, initialized to a large value.
• Base Case: dp[0][0] = 0, as partitioning an empty string into 0 parts costs 0.
• Transition: We fill the DP table by iterating through the number of partitions p, the prefix length i, and the split point j. The last partition is s[j...i-1], and the first p-1 partitions cover s[0...j-1]. The constraints k <= n/2 imply that each partition can have a length of at least 2. This helps define the loop bounds for i and j to ensure valid partitions.

dp[i][p] = min(dp[i][p], dp[j][p-1] + min_costs[j][i-1])

1int[][] dp = new int[n + 1][k + 1];2for (int[] row : dp) {3    Arrays.fill(row, n + 1); // A value larger than any possible cost4}5dp[0][0] = 0;6 7for (int p = 1; p <= k; p++) {8    for (int i = 2 * p; i <= n; i++) {9        for (int j = 2 * (p - 1); j <= i - 2; j++) {10            dp[i][p] = Math.min(dp[i][p], dp[j][p - 1] + min_costs[j][i - 1]);11        }12    }13}14return dp[n][k];