337. Palindrome Partitioning III

Precompute cost[i][j] = characters to change to make s[i..j] a palindrome. Then dp[i][j] = min changes to split the first i characters into j palindromic parts, choosing where the last part begins.

Step 1 — cost to make any substring a palindrome

cost[i][j] = the number of character changes needed to turn s[i..j] into a palindrome. A substring is fixed by matching its ends inward, so:

cost[i][j] = cost[i+1][j-1] + (0 if s[i] == s[j] else 1)

with cost[i][i] = 0 and cost[i][i+1] = (s[i] != s[i+1]). Fill by increasing length.

Step 2 — partition DP

Let dp[i][j] = the minimum changes to split the first i characters into exactly j palindromic parts. The last (j-th) part is s[p..i-1] for some split point p; before it, the first p characters form j-1 parts:

dp[i][j] = min over p in [j-1, i-1] of ( dp[p][j-1] + cost[p][i-1] )

Base: dp[0][0] = 0; everything else starts at infinity. The answer is dp[n][k].

Worked example

s = "abcde", k = 3.

Every single character is already a palindrome (cost 0), and pairs like "bc" cost 1. The best split into 3 parts is e.g. "a" | "b" | "cde", where "cde" needs 1 change (c↔e), giving a total of 1. No 3-way split does better, so the answer is 1.

Complexity

• Time: O(n^2 · k) for the partition DP (plus O(n^2) for the cost table).
• Space: O(n^2 + n·k).

class Solution {
    public int palindromePartition(String s, int k) {
        int n = s.length();
        // cost[i][j] = changes to make s[i..j] a palindrome.
        int[][] cost = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                cost[i][j] = cost[i + 1][j - 1] + (s.charAt(i) == s.charAt(j) ? 0 : 1);
            }
        }
        int INF = Integer.MAX_VALUE / 2;
        int[][] dp = new int[n + 1][k + 1];
        for (int[] row : dp) Arrays.fill(row, INF);
        dp[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= Math.min(i, k); j++) {
                for (int p = j - 1; p < i; p++) {
                    if (dp[p][j - 1] != INF) {
                        dp[i][j] = Math.min(dp[i][j], dp[p][j - 1] + cost[p][i - 1]);
                    }
                }
            }
        }
        return dp[n][k];
    }
}