# Palindrome Partitioning III
**Difficulty:** HARD
[External](https://leetcode.com/problems/palindrome-partitioning-iii)
Canonical: https://scaleengineer.com/dsa/problems/palindrome-partitioning-iii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
---
## Problem
You are given a string `s` containing lowercase letters and an integer `k`. You need to :

* First, change some characters of `s` to other lowercase English letters.
* Then divide `s` into `k` non-empty disjoint substrings such that each substring is a palindrome.

Return _the minimal number of characters that you need to change to divide the string_.

**Example 1:**

**Input:** s = "abc", k = 2
**Output:** 1
**Explanation:** You can split the string into "ab" and "c", and change 1 character in "ab" to make it palindrome.

**Example 2:**

**Input:** s = "aabbc", k = 3
**Output:** 0
**Explanation:** You can split the string into "aa", "bb" and "c", all of them are palindrome.

**Example 3:**

**Input:** s = "leetcode", k = 8
**Output:** 0

**Constraints:**

* `1 <= k <= s.length <= 100`.
* `s` only contains lowercase English letters.

# Approaches
## Brute-Force Recursion
This approach explores all possible ways to partition the string `s` into `k` non-empty substrings. For each partitioning scheme, it calculates the total number of character changes required to make every substring a palindrome and finds the minimum among all schemes. This is done using a recursive helper function that does not use memoization.
**Time:** Exponential. The number of ways to partition a string of length `n` into `k` parts is given by the stars and bars formula, `C(n-1, k-1)`. For each partition, we spend `O(n^2)` to calculate costs. The complexity is roughly `O(C(n-1, k-1) * n^2)`, which is too slow for the given constraints. · **Space:** O(n) or O(k) for the recursion stack depth, where n is the length of the string.
**Pros:** Conceptually simple to understand as it directly models the problem statement.
**Cons:** Extremely inefficient due to recomputing the same subproblems.; Will result in a 'Time Limit Exceeded' (TLE) error for most test cases due to its exponential time complexity.
### Explanation
We define a recursive function, say `solve(index, partitions_left)`. This function calculates the minimum cost to partition the suffix of the string starting at `index` into `partitions_left` palindromic substrings.

The base cases for the recursion are:
- If `partitions_left` is 1, we must use the entire remaining string `s[index...n-1]` as the last partition. The cost is the number of changes to make this substring a palindrome.
- If we run out of characters (`index == n`) but still need to make partitions (`partitions_left > 0`), or vice-versa, it's an invalid state. We return a very large value (infinity) to signify this.

In the recursive step, we try all possible split points for the current partition. We can form the first substring of the current suffix `s[index...n-1]` as `s[index...j]`, where `j` varies from `index` up to a point that leaves enough characters for the remaining partitions.

For each choice of `j`, we calculate the cost to make `s[index...j]` a palindrome. Then, we recursively call the function for the rest of the string `s[j+1...n-1]` with `partitions_left - 1`.

The cost to make a substring a palindrome is calculated by comparing characters from both ends and counting the mismatches.

The function returns the minimum cost found among all possible split points `j`. This approach is highly inefficient because it recomputes the results for the same subproblems (same `index` and `partitions_left`) multiple times, leading to an exponential time complexity.
### Algorithm
- Create a helper function `calculateCost(s, i, j)` that computes the minimum changes to make substring `s[i...j]` a palindrome. It iterates from both ends inwards, counting mismatches.
- Create a recursive function `solve(s, k, index)`.
- **Base Case 1:** If `k == 1`, the only option is to make the rest of the string `s[index...n-1]` a palindrome. Return `calculateCost(s, index, n-1)`.
- **Base Case 2:** If `index >= s.length()` or `k <= 0`, it's an invalid state, return a large value to indicate impossibility.
- Initialize `minChanges` to a very large value.
- Iterate `j` from `index` to `s.length() - k`. This `j` represents the end index of the first of the `k` partitions.
- For each `j`, calculate `currentCost = calculateCost(s, index, j)`.
- Recursively call `remainingCost = solve(s, k - 1, j + 1)` to find the cost for the rest of the string.
- Update `minChanges = min(minChanges, currentCost + remainingCost)`.
- Return `minChanges`.
- The initial call to start the process is `solve(s, k, 0)`.

## Dynamic Programming with Memoization
This approach improves upon the brute-force recursion by using memoization (a top-down dynamic programming technique) to store and reuse the results of subproblems. This avoids redundant computations and significantly reduces the time complexity. We also precompute the costs of making any substring a palindrome to speed up the main DP calculation.
**Time:** O(n^2) for precomputing costs + `O(n^2 * k)` for the DP/memoized recursion. The total time complexity is dominated by the DP part, so it's `O(n^2 * k)`. Given `n <= 100` and `k <= 100`, this is efficient enough. · **Space:** O(n^2) for the `cost` table and `O(n * k)` for the `memo` or `dp` table. The total space complexity is `O(n^2)` as `n >= k`.
**Pros:** Guaranteed to find the optimal solution.; Efficient enough to pass within the time limits for the given constraints.
**Cons:** Requires more space compared to the brute-force approach due to the memoization and cost tables.; The logic is slightly more complex to implement than a simple recursive solution.
### Explanation
The core idea is to solve the problem recursively but store the results of subproblems to avoid re-computation. We define a function `solve(i, k)` which computes the minimum changes to partition the suffix `s[i...n-1]` into `k` palindromic substrings.

First, to avoid repeatedly calculating the cost of making a substring a palindrome, we precompute these values. A 2D array, `cost[i][j]`, stores the minimum changes for `s[i...j]`. This can be done efficiently in `O(n^2)` time using a DP relation: `cost[i][j] = cost[i+1][j-1] + (s[i] == s[j] ? 0 : 1)`.

Next, we set up the memoized recursion. The state is defined by `(i, k)`, the starting index and the number of partitions remaining. We use a 2D array `memo[i][k]` to store the results.

In the `solve(i, k)` function:
1.  We handle base cases: if we need to partition an empty string, or if we don't have enough characters for the required partitions.
2.  We check if `memo[i][k]` already contains a valid result. If so, we return it.
3.  If not, we compute the result by trying all possible split points `j` for the first partition `s[i...j]`. For each `j`, the total cost is `cost[i][j]` plus the result of the recursive call for the rest of the string, `solve(j + 1, k - 1)`.
4.  We take the minimum cost over all possible `j`.
5.  Finally, we store this minimum cost in `memo[i][k]` before returning it.

This approach ensures that each of the `O(n * k)` subproblems is solved only once, making it efficient enough for the given constraints.

```java
class Solution {
    private int[][] cost;
    private int[][] memo;
    private int n;
    private String s;

    public int palindromePartition(String s, int k) {
        this.n = s.length();
        this.s = s;
        this.cost = new int[n][n];
        this.memo = new int[n][k + 1];

        // Precompute the cost to make any substring a palindrome
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                cost[i][j] = calculateCost(i, j);
            }
        }
        
        // Initialize memoization table with -1
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                memo[i][j] = -1;
            }
        }

        return solve(0, k);
    }

    private int calculateCost(int i, int j) {
        int changes = 0;
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                changes++;
            }
            i++;
            j--;
        }
        return changes;
    }

    private int solve(int i, int k) {
        // Base case: If we have partitioned the whole string
        if (i == n) {
            return k == 0 ? 0 : 101; // Return 0 if k is also 0, else a large value
        }
        // Base case: Not enough characters left for remaining partitions or no partitions left
        if (n - i < k || k == 0) {
            return 101; // A value larger than max possible cost (100)
        }
        // Base case: Only one partition left, must use the rest of the string
        if (k == 1) {
            return cost[i][n - 1];
        }
        // Memoization check
        if (memo[i][k] != -1) {
            return memo[i][k];
        }

        int minChanges = 101;
        // Iterate through all possible split points 'j' for the current partition
        for (int j = i; j <= n - k; j++) {
            int currentCost = cost[i][j];
            int remainingCost = solve(j + 1, k - 1);
            minChanges = Math.min(minChanges, currentCost + remainingCost);
        }

        return memo[i][k] = minChanges;
    }
}
```

An alternative is to use a bottom-up DP approach, which is iteratively fills a DP table and is sometimes preferred for avoiding recursion overhead.

```java
class Solution {
    public int palindromePartition(String s, int k) {
        int n = s.length();
        int[][] cost = new int[n][n];
        // Precompute cost to make s[i..j] a palindrome
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                cost[i][j] = cost[i + 1][j - 1] + (s.charAt(i) == s.charAt(j) ? 0 : 1);
            }
        }

        // dp[i][p] = min cost to partition s[0...i-1] into p parts
        int[][] dp = new int[n + 1][k + 1];
        for (int i = 0; i <= n; i++) {
            for (int p = 0; p <= k; p++) {
                dp[i][p] = 101; // Initialize with a large value
            }
        }
        dp[0][0] = 0;

        for (int p = 1; p <= k; p++) {
            for (int i = 1; i <= n; i++) {
                // Last partition is s[j...i-1]
                for (int j = 0; j < i; j++) {
                    if (dp[j][p - 1] != 101) {
                       dp[i][p] = Math.min(dp[i][p], dp[j][p - 1] + cost[j][i - 1]);
                    }
                }
            }
        }
        return dp[n][k];
    }
}
```
### Algorithm
- **Precomputation:** Create a 2D array `cost[n][n]`. Iterate through all possible substrings `s[i...j]` and calculate the minimum changes needed to make them a palindrome. Store this value in `cost[i][j]`. This can be done in `O(n^2)`.
- **Memoization:** Create a 2D array `memo[n][k+1]` initialized with a value indicating that the state has not been computed (e.g., -1).
- **Recursive Function with Memoization:** Define a function `solve(i, k)` that computes the minimum cost to partition the suffix `s[i...n-1]` into `k` parts.
- **Base Cases:**
    - If we have partitioned the whole string (`i == n`), return 0 if `k` is also 0, otherwise return a large value (infinity).
    - If there are not enough characters left for the remaining partitions (`n - i < k`) or we need to partition into 0 parts before reaching the end (`k == 0`), return infinity.
    - If only one partition is left (`k == 1`), we must use the rest of the string, so return `cost[i][n-1]`.
- **Memoization Check:** If `memo[i][k]` has been computed, return the stored value.
- **Recursive Step:**
    - Initialize `minChanges` to a large value.
    - Iterate `j` from `i` to `n - k`. This `j` is the end of the first partition.
    - Calculate `currentTotalChanges = cost[i][j] + solve(j + 1, k - 1)`.
    - Update `minChanges = min(minChanges, currentTotalChanges)`.
- **Store and Return:** Store the result in `memo[i][k]` and return it.
- The initial call is `solve(0, k)`.

# Solutions
### Java

```java
class Solution {
public
  int palindromePartition(String s, int k) {
    int n = s.length();
    int[][] g = new int[n][n];
    for (int i = n - 1; i >= 0; --i) {
      for (int j = i; j < n; ++j) {
        g[i][j] = s.charAt(i) != s.charAt(j) ? 1 : 0;
        if (i + 1 < j) {
          g[i][j] += g[i + 1][j - 1];
        }
      }
    }
    int[][] f = new int[n + 1][k + 1];
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= Math.min(i, k); ++j) {
        if (j == 1) {
          f[i][j] = g[0][i - 1];
        } else {
          f[i][j] = 10000;
          for (int h = j - 1; h < i; ++h) {
            f[i][j] = Math.min(f[i][j], f[h][j - 1] + g[h][i - 1]);
          }
        }
      }
    }
    return f[n][k];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int palindromePartition(string s, int k) {
    int n = s.size();
    vector<vector<int>> g(n, vector<int>(n));
    for (int i = n - 1; i >= 0; --i) {
      for (int j = i; j < n; ++j) {
        g[i][j] = s[i] != s[j] ? 1 : 0;
        if (i + 1 < j)
          g[i][j] += g[i + 1][j - 1];
      }
    }
    vector<vector<int>> f(n + 1, vector<int>(k + 1));
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= min(i, k); ++j) {
        if (j == 1) {
          f[i][j] = g[0][i - 1];
        } else {
          f[i][j] = 10000;
          for (int h = j - 1; h < i; ++h) {
            f[i][j] = min(f[i][j], f[h][j - 1] + g[h][i - 1]);
          }
        }
      }
    }
    return f[n][k];
  }
};

```

### Python

```python
class Solution:
    def palindromePartition(self, s: str, k: int) -> int: n = len(s) g = [[0] * n for _ in range(n)] for i in range(n - 1, - 1, - 1): for j in range(i + 1, n): g[i][j] = int(s[i] != s[j]) if i + 1 < j: g[i][j] += g[i + 1][j - 1] f = [[0] * (k + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(1, min(i, k) + 1): if j == 1: f[i][j] = g[0][i - 1] else: f[i][j] = inf for h in range(j - 1, i): f[i][j] = min(f[i][j], f[h][j - 1] + g[h][i - 1]) return f[n][k]

```