Palindrome Partitioning II

Description

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.

Primary Approach: Expand Around Center DP ($O(N^2)$ Time, $O(N)$ Space)

Intuition

To solve 132. Palindrome Partitioning II, define cuts[i] as the minimum cuts required to partition the prefix s[0 ... i] into palindromic substrings:

1. Worst-Case Initialization: Initialize cuts[i] = i because cutting every single character requires at most i cuts for a prefix of length i + 1.
2. Expand Around Center: Every palindrome has a center. Iterating through each index mid as a potential palindrome center allows us to expand outward to discover all palindromic substrings s[left ... right]:
   • Odd Length Palindromes: Center at (mid, mid).
   • Even Length Palindromes: Center at (mid, mid + 1).
3. Transition: Whenever s[left ... right] is a valid palindrome:
   • If left == 0, the whole prefix s[0 ... right] is a palindrome, so cuts[right] = 0.
   • Otherwise, cuts[right] = min(cuts[right], cuts[left - 1] + 1).

class Solution {
    public int minCut(String s) {
        int n = s.length();
        int[] cuts = new int[n];
 
        // Max possible cuts for s[0...i] is i (cutting into individual characters)
        for (int i = 0; i < n; i++) {
            cuts[i] = i;
        }
 
        for (int mid = 0; mid < n; mid++) {
            // Odd length palindromes (centered at mid)
            expandAndCalculate(s, mid, mid, cuts);
 
            // Even length palindromes (centered at mid, mid + 1)
            expandAndCalculate(s, mid, mid + 1, cuts);
        }
 
        return cuts[n - 1];
    }
 
    private void expandAndCalculate(String s, int left, int right, int[] cuts) {
        int n = s.length();
 
        while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
            if (left == 0) {
                // Entire prefix s[0...right] is a palindrome
                cuts[right] = 0;
            } else {
                cuts[right] = Math.min(cuts[right], cuts[left - 1] + 1);
            }
            left--;
            right++;
        }
    }
}
 

Complexity

• Time Complexity: $O(N^2)$ — Expanding around all $2N-1$ possible centers takes $O(N)$ time per center.
• Space Complexity: $O(N)$ auxiliary space — Only uses a single 1D array cuts of size $N$.

---

Alternative Approach: 2D Palindrome Table + 1D DP ($O(N^2)$ Time, $O(N^2)$ Space)

Intuition

Split the subproblems into two clear steps:

1. Precompute Palindromes: Use a 2D boolean table isPal[j][i] where isPal[j][i] = true if s[j ... i] is a palindrome. A substring s[j ... i] is a palindrome if s.charAt(j) == s.charAt(i) AND (i - j <= 2 OR isPal[j + 1][i - 1] is true).
2. Compute Minimum Cuts: Iterate i from $0$ to $N-1$. If isPal[0][i] is true, cuts[i] = 0. Otherwise, test all split points j from $0$ to $i-1$:

$\text{cuts}[i]={\min }_{0\le j<i\text{ and }\text{isPal}[j+1][i]}(\text{cuts}[i],\text{cuts}[j]+1)$

class Solution {
    public int minCut(String s) {
        int n = s.length();
        boolean[][] isPal = new boolean[n][n];
        int[] cuts = new int[n];
 
        for (int i = 0; i < n; i++) {
            int minCuts = i; // Max cuts needed is i
 
            for (int j = 0; j <= i; j++) {
                if (s.charAt(j) == s.charAt(i) && (i - j <= 2 || isPal[j + 1][i - 1])) {
                    isPal[j][i] = true;
 
                    if (j == 0) {
                        minCuts = 0;
                    } else {
                        minCuts = Math.min(minCuts, cuts[j - 1] + 1);
                    }
                }
            }
            cuts[i] = minCuts;
        }
 
        return cuts[n - 1];
    }
}
 

Complexity

• Time Complexity: $O(N^2)$ — Nested loop over string length $N$.
• Space Complexity: $O(N^2)$ auxiliary space — Required for the 2D matrix isPal.

---

Key Interview Discussion Points

• Space Advantage of Expand Around Center: The Expand Around Center approach computes palindrome validity dynamically without building a full $O(N^2)$ matrix, cutting auxiliary space down to $O(N)$.
• Comparison with Palindrome Partitioning I: While 131. Palindrome Partitioning asks for all possible valid partitions (requiring $O(2^N)$ backtracking), this problem only asks for the minimum number of cuts, making Dynamic Programming $O(N^2)$ optimal.

---

Easy Memory Rule

“Expand center $\to$ If s[left ... right] is palindrome $\to$ cuts[right] = min(cuts[right], cuts[left - 1] + 1)!”