# Minimum Changes to Make K Semi-palindromes
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-changes-to-make-k-semi-palindromes)
Canonical: https://scaleengineer.com/dsa/problems/minimum-changes-to-make-k-semi-palindromes
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
---
## 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:​

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

Consider the string `"abcabc"`:

* The length of `"abcabc"` is `6`. Valid divisors are `1`, `2`, and `3`.
* For `d = 1`: The entire string `"abcabc"` forms one group. Not a palindrome.
* For `d = 2`:  
  * Group 1 (positions `1, 3, 5`): `"acb"`
  * Group 2 (positions `2, 4, 6`): `"bac"`
  * Neither group forms a palindrome.
* 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. Therefore, `"abcabc"` is a semi-palindrome.

**Example 1:** 

**Input:**  s = "abcac", k = 2 

**Output:**  1 

**Explanation:**  Divide `s` into `"ab"` and `"cac"`. `"cac"` is already semi-palindrome. Change `"ab"` to `"aa"`, it becomes semi-palindrome with `d = 1`.

**Example 2:** 

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

**Output:**  2 

**Explanation:**  Divide `s` into substrings `"abc"` and `"def"`. Each needs one change to become semi-palindrome.

**Example 3:** 

**Input:**  s = "aabbaa", k = 3 

**Output:**  0 

**Explanation:**  Divide `s` into substrings `"aa"`, `"bb"` and `"aa"`. All are already semi-palindromes.

**Constraints:**

* `2 <= s.length <= 200`
* `1 <= k <= s.length / 2`
* `s` contains only lowercase English letters.

# Approaches
## Brute-Force Recursive Approach
A brute-force approach involves exploring every possible way to partition the string `s` into `k` substrings. This can be implemented using a recursive function. The function would try every possible length for the current substring, calculate the cost to make it a semi-palindrome, and then recursively solve the problem for the rest of the string with one fewer partition. This method is straightforward to conceptualize but is highly inefficient as it recalculates results for the same subproblems multiple times.
**Time:** Exponential, roughly O(C(n-1, k-1) * n^2), where n is the string length. This is because it explores all C(n-1, k-1) partitions and for each, it calculates substring costs. · **Space:** O(k), for the recursion stack depth.
**Pros:** Simple to understand and implement as it directly models the problem's definition.; Serves as a good starting point for developing a more optimized dynamic programming solution.
**Cons:** Extremely inefficient due to a large number of redundant computations for the same subproblems.; The time complexity is exponential, making it infeasible for the given constraints.; Will result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
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)`.

```java
class Solution {
    public int minimumChanges(String s, int k) {
        return solve(s, 0, k);
    }

    private int calculateCost(String sub) {
        int len = sub.length();
        if (len < 2) return Integer.MAX_VALUE / 2;

        List<Integer> divs = new ArrayList<>();
        for (int d = 1; d < len; d++) {
            if (len % d == 0) divs.add(d);
        }
        if (divs.isEmpty()) return Integer.MAX_VALUE / 2;

        int minChanges = len;
        for (int d : divs) {
            int currentChanges = 0;
            for (int rem = 0; rem < d; rem++) {
                int groupLen = len / d;
                for (int p = 0; p < groupLen / 2; p++) {
                    if (sub.charAt(rem + p * d) != sub.charAt(rem + (groupLen - 1 - p) * d)) {
                        currentChanges++;
                    }
                }
            }
            minChanges = Math.min(minChanges, currentChanges);
        }
        return minChanges;
    }

    private int solve(String s, int index, int parts_left) {
        int n = s.length();
        if (parts_left == 0) {
            return index == n ? 0 : Integer.MAX_VALUE / 2;
        }
        // Each of the remaining 'parts_left' partitions must have length at least 2.
        if (n - index < 2 * parts_left) {
            return Integer.MAX_VALUE / 2;
        }

        int minTotalCost = Integer.MAX_VALUE / 2;
        // The current partition s[index...i] must leave enough characters for the rest.
        for (int i = index; i <= n - 2 * parts_left; i++) {
            String sub = s.substring(index, i + 1);
            int currentCost = calculateCost(sub);
            if (currentCost < Integer.MAX_VALUE / 2) {
                int remainingCost = solve(s, i + 1, parts_left - 1);
                if (remainingCost < Integer.MAX_VALUE / 2) {
                    minTotalCost = Math.min(minTotalCost, currentCost + remainingCost);
                }
            }
        }
        return minTotalCost;
    }
}
```
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.
### Algorithm
- 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)`.

## Dynamic Programming with Precomputation
This problem has optimal substructure and overlapping subproblems, making it a perfect candidate for dynamic programming. The core idea is to build up a solution for `k` partitions using solutions for `k-1` partitions. We define `dp[i][p]` as the minimum cost to partition the prefix `s[0...i-1]` into `p` semi-palindromes. To compute `dp[i][p]`, we try all possible split points `j`, where `s[j...i-1]` is the last partition, and take the minimum over `dp[j][p-1] + cost(s[j...i-1])`. To avoid recomputing the cost of making a substring a semi-palindrome repeatedly, we can precompute these costs for all possible substrings and store them in a lookup table. This precomputation, while intensive, allows the DP phase to run efficiently.
**Time:** O(n^3 * log n + k * n^2). The precomputation of costs is O(n^3 * log n) on average, and the DP calculation is O(k * n^2). · **Space:** O(n^2), dominated by the `min_costs` table. The `dp` table takes O(n*k) space.
**Pros:** Guarantees finding the globally optimal solution.; Efficient enough for the given constraints (`n <= 200`).; The use of precomputation avoids redundant calculations within the DP loops.
**Cons:** The precomputation step has a relatively high time complexity, `O(n^3 * log n)`.; Requires `O(n^2)` space for the precomputed costs table, which can be large for bigger `n`.
### Explanation
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`.

```java
// Precomputing divisors for efficiency
List<Integer>[] divisors = new List[n + 1];
for (int i = 1; i <= n; i++) {
    divisors[i] = new ArrayList<>();
    for (int j = 1; j * j <= i; j++) {
        if (i % j == 0) {
            if (j < i) divisors[i].add(j);
            if (i / j != j && i / j < i) divisors[i].add(i / j);
        }
    }
}

// Precomputing costs for all substrings
int[][] min_costs = new int[n][n];
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        int len = j - i + 1;
        int current_min = len; // A safe upper bound
        for (int d : divisors[len]) {
            int changes = 0;
            for (int rem = 0; rem < d; rem++) {
                int group_len = len / d;
                for (int p = 0; p < group_len / 2; p++) {
                    if (s.charAt(i + rem + p * d) != s.charAt(i + rem + (group_len - 1 - p) * d)) {
                        changes++;
                    }
                }
            }
            current_min = Math.min(current_min, changes);
        }
        min_costs[i][j] = current_min;
    }
}
```

### 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])`

```java
int[][] dp = new int[n + 1][k + 1];
for (int[] row : dp) {
    Arrays.fill(row, n + 1); // A value larger than any possible cost
}
dp[0][0] = 0;

for (int p = 1; p <= k; p++) {
    for (int i = 2 * p; i <= n; i++) {
        for (int j = 2 * (p - 1); j <= i - 2; j++) {
            dp[i][p] = Math.min(dp[i][p], dp[j][p - 1] + min_costs[j][i - 1]);
        }
    }
}
return dp[n][k];
```
### Algorithm
- **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]`.

# Solutions
### Java

```java
class Solution {
public
  int minimumChanges(String s, int k) {
    int n = s.length();
    int[][] g = new int[n + 1][n + 1];
    int[][] f = new int[n + 1][k + 1];
    final int inf = 1 << 30;
    for (int i = 0; i <= n; ++i) {
      Arrays.fill(g[i], inf);
      Arrays.fill(f[i], inf);
    }
    for (int i = 1; i <= n; ++i) {
      for (int j = i; j <= n; ++j) {
        int m = j - i + 1;
        for (int d = 1; d < m; ++d) {
          if (m % d == 0) {
            int cnt = 0;
            for (int l = 0; l < m; ++l) {
              int r = (m / d - 1 - l / d) * d + l % d;
              if (l >= r) {
                break;
              }
              if (s.charAt(i - 1 + l) != s.charAt(i - 1 + r)) {
                ++cnt;
              }
            }
            g[i][j] = Math.min(g[i][j], cnt);
          }
        }
      }
    }
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= k; ++j) {
        for (int h = 0; h < i - 1; ++h) {
          f[i][j] = Math.min(f[i][j], f[h][j - 1] + g[h + 1][i]);
        }
      }
    }
    return f[n][k];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumChanges(string s, int k) {
    int n = s.size();
    int g[n + 1][n + 1];
    int f[n + 1][k + 1];
    memset(g, 0x3f, sizeof(g));
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
      for (int j = i; j <= n; ++j) {
        int m = j - i + 1;
        for (int d = 1; d < m; ++d) {
          if (m % d == 0) {
            int cnt = 0;
            for (int l = 0; l < m; ++l) {
              int r = (m / d - 1 - l / d) * d + l % d;
              if (l >= r) {
                break;
              }
              if (s[i - 1 + l] != s[i - 1 + r]) {
                ++cnt;
              }
            }
            g[i][j] = min(g[i][j], cnt);
          }
        }
      }
    }
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= k; ++j) {
        for (int h = 0; h < i - 1; ++h) {
          f[i][j] = min(f[i][j], f[h][j - 1] + g[h + 1][i]);
        }
      }
    }
    return f[n][k];
  }
};

```

### Python

```python
class Solution:
    def minimumChanges(self, s: str, k: int) -> int: n = len(s) g = [[inf] * (n + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(i, n + 1): m = j - i + 1 for d in range(1, m): if m % d == 0: cnt = 0 for l in range(m): r = (m // d - 1 - l // d) * d + l % d if l >= r: break if s[i - 1 + l] != s[i - 1 + r]: cnt += 1 g[i][j] = min(g[i][j], cnt) f = [[inf] * (k + 1) for _ in range(n + 1)] f[0][0] = 0 for i in range(1, n + 1): for j in range(1, k + 1): for h in range(i - 1): f[i][j] = min(f[i][j], f[h][j - 1] + g[h + 1][i]) return f[n][k]

```