LeetCode 1278: Palindrome Partitioning III

Explanation:

To solve this problem, we can use dynamic programming to find the minimum number of characters that need to be changed to partition the string into k non-empty disjoint palindromic substrings.

We can define a 2D dp array where dp[i][j] represents the minimum number of characters that need to be changed to partition the substring s[0:i] into j palindromic substrings.

The algorithm involves iterating over all possible substring lengths and partition counts, and at each step, we update the dp array based on the optimal number of changes needed to partition the current substring.

The final answer will be stored in dp[n][k], where n is the length of the input string s.

Steps:

1. Initialize a 2D dp array of size (n+1) x (k+1) where n is the length of the string s.
2. Initialize the base cases: dp[i][1] = the number of changes needed to partition s[0:i] into 1 palindromic substring.
3. Iterate over all possible substring lengths and partition counts to update the dp array based on the optimal number of changes.
4. Return dp[n][k] as the final answer.

Time Complexity:

The time complexity of this algorithm is O(n^2 * k) where n is the length of the input string s.

Space Complexity:

The space complexity of this algorithm is O(n * k) where n is the length of the input string s.

:

class Solution {
    public int palindromePartition(String s, int k) {
        int n = s.length();
        int[][] dp = new int[n+1][k+1];
        
        for (int i = 1; i <= n; i++) {
            dp[i][1] = costToPalindrome(s.substring(0, i));
        }
        
        for (int i = 1; i <= n; i++) {
            for (int j = 2; j <= k; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                for (int l = 1; l < i; l++) {
                    dp[i][j] = Math.min(dp[i][j], dp[l][j-1] + costToPalindrome(s.substring(l, i)));
                }
            }
        }
        
        return dp[n][k];
    }
    
    private int costToPalindrome(String str) {
        int cost = 0;
        int i = 0, j = str.length() - 1;
        
        while (i < j) {
            if (str.charAt(i) != str.charAt(j)) {
                cost++;
            }
            i++;
            j--;
        }
        
        return cost;
    }
}