LeetCode Hard – Palindrome Partitioning II

Given a string s, partition s such that every 

substring of the partition is a 

palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example 1:

Input: s = “aab”

Output: 1

Explanation: The palindrome partitioning [“aa”,”b”] could be produced using 1 cut.

Example 2:

Input: s = “a”

Output: 0

Example 3:

Input: s = “ab”

Output: 1

Constraints:

• 1 <= s.length <= 2000
• s consists of lowercase English letters only.

Java Solution

To solve this problem, you can use dynamic programming to find the minimum cuts needed for a palindrome partitioning of the string s. The idea is to create a table to store information about whether each substring is a palindrome, and then use this information to determine the minimum cuts.

Here’s the Java solution:

public class PalindromePartitioningII {
    public int minCut(String s) {
        int n = s.length();
        boolean[][] isPalindrome = new boolean[n][n];

        // Initialize the table for palindrome checking
        for (int len = 1; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                isPalindrome[i][j] = s.charAt(i) == s.charAt(j) && (len <= 2 || isPalindrome[i + 1][j - 1]);
            }
        }

        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = i;  // Worst case: one cut for each character
        }

        for (int i = 1; i < n; i++) {
            for (int j = i; j >= 0; j--) {
                if (isPalindrome[j][i]) {
                    dp[i] = (j == 0) ? 0 : Math.min(dp[i], dp[j - 1] + 1);
                }
            }
        }

        return dp[n - 1];
    }

    public static void main(String[] args) {
        PalindromePartitioningII solution = new PalindromePartitioningII();

        // Example 1
        String s1 = "aab";
        System.out.println(solution.minCut(s1));  // Output: 1

        // Example 2
        String s2 = "a";
        System.out.println(solution.minCut(s2));  // Output: 0

        // Example 3
        String s3 = "ab";
        System.out.println(solution.minCut(s3));  // Output: 1
    }
}

This Java code defines a PalindromePartitioningII class with the minCut method, which uses dynamic programming to find the minimum cuts needed for a palindrome partitioning of the input string s. The provided test cases demonstrate its usage.

Python Solution

Here’s the equivalent Python solution for finding the minimum cuts needed for a palindrome partitioning:

class PalindromePartitioningII:
    def minCut(self, s: str) -> int:
        n = len(s)
        is_palindrome = [[False] * n for _ in range(n)]

        # Initialize the table for palindrome checking
        for length in range(1, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                is_palindrome[i][j] = s[i] == s[j] and (length <= 2 or is_palindrome[i + 1][j - 1])

        dp = [i for i in range(n)]

        for i in range(1, n):
            for j in range(i, -1, -1):
                if is_palindrome[j][i]:
                    dp[i] = 0 if j == 0 else min(dp[i], dp[j - 1] + 1)

        return dp[n - 1]

# Test cases
solution = PalindromePartitioningII()

# Example 1
s1 = "aab"
print(solution.minCut(s1))  # Output: 1

# Example 2
s2 = "a"
print(solution.minCut(s2))  # Output: 0

# Example 3
s3 = "ab"
print(solution.minCut(s3))  # Output: 1

This Python code defines a PalindromePartitioningII class with the minCut method, which uses dynamic programming to find the minimum cuts needed for a palindrome partitioning of the input string s. The provided test cases demonstrate its usage.