Palindrome Partitioning Iii - Leetcode Solution

Problem Statement: Given a string s and an integer k, partition s such that every substring of the partition is a palindrome. Return the minimum number of cuts needed for a palindrome partitioning of s.

Example 1: Input: s = "aab", k = 1 Output: 1 Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Example 2: Input: s = "leetcode", k = 8 Output: 0 Explanation: s is already a palindrome.

Solution:

We can solve the problem using dynamic programming. Our aim is to minimize the number of cuts needed to partition the given string into k parts. Let dp[i][j] represent the minimum number of cuts needed to partition s[i..j] into k parts.

To compute dp[i][j], we can iterate over all possible index positions mid such that i <= mid <= j. Let us assume that we partition the string s[i..j] at index mid. If the substring s[i..mid] is not a palindrome, we cannot partition it further. Hence, we can increment the index position mid. Otherwise, we can attempt to partition the remaining substring s[mid+1..j], making k-1 partitions, and add the number of cuts needed to partition this substring to dp[i][mid].

Finally, we can take the minimum value of dp[i][j] over all i <= j, and return dp[0][n-1].

Let us also compute the cost to determine whether a substring from index i to index j is a palindrome. We can do this using a boolean array isPalin[n][n]. We can compute isPalin as follows:

for (int len = 1; len <= n; len++) { for (int i = 0, j = i+len-1; j < n; i++, j++) { isPalin[i][j] = (s[i] == s[j]) && (len <= 2 || isPalin[i+1][j-1]); } }

Time Complexity: The time complexity of the above approach is O(n^3) because for each substring, we need to iterate over all possible mid positions. The cost to determine if a substring is a palindrome is O(n^2). Hence, the overall time complexity is O(n^3 + n^2) = O(n^3).

Space Complexity: The space complexity of the above approach is O(n^2), which is used to store the dp and isPalin arrays.

Code Implementation:

public int palindromePartition(String s, int k) { int n = s.length(); if (n == k) return 0; // no cuts needed if k equals length of string int[][] dp = new int[n][k+1]; boolean[][] isPalin = new boolean[n][n]; for (int len = 1; len <= n; len++) { for (int i = 0, j = i+len-1; j < n; i++, j++) { isPalin[i][j] = (s.charAt(i) == s.charAt(j)) && (len <= 2 || isPalin[i+1][j-1]); } } for (int i = 0; i < n; i++) { Arrays.fill(dp[i], n); // initialize to a very large value } for (int i = 0; i < n; i++) { dp[i][1] = cutCost(isPalin, i, n-1); for (int j = 2; j <= k; j++) { for (int mid = i; mid < n-1; mid++) { dp[i][j] = Math.min(dp[i][j], dp[mid+1][j-1] + cutCost(isPalin, i, mid)); } } } return dp[0][k]; }

private int cutCost(boolean[][] isPalin, int i, int j) { if (isPalin[i][j]) return 0; int cuts = 0; for (int k = i; k < j; k++) { if (isPalin[i][k] && isPalin[k+1][j]) { cuts++; // optional optimization: break early if palindrome found // if (cuts > 1) break; } } return cuts; }

Test Cases: Let us test the function against the example test cases given in the problem statement.

Example 1: String s = "aab", k = 1 int expectedOutput = 1 int actualOutput = palindromePartition(s, k) assert actualOutput == expectedOutput

Example 2: String s = "leetcode", k = 8 int expectedOutput = 0 int actualOutput = palindromePartition(s, k) assert actualOutput == expectedOutput

Conclusion: In this post, we have solved the Palindrome Partitioning III problem on LeetCode using dynamic programming. The problem requires finding the minimum number of cuts needed to partition a string into k parts such that every substring is a palindrome. We have used dp[i][j] to represent the minimum number of cuts needed to partition s[i..j] with k parts. The time complexity of our solution is O(n^3) and the space complexity is O(n^2). The function passes all the example test cases.

1