Palindrome Partitioning II

Problem Statement

Imagine you’re a word sculptor with a string and a mission: slice it into the fewest possible pieces, each a perfect palindrome. This hard-level DP challenge is all about symmetry—how few cuts can you make to turn chaos into mirrored masterpieces? Given a string, return the minimum number of cuts needed.

Example

Input: s = "aab"

Output: 1 (Cut into "aa" | "b")

Input: s = "a"

Output: 0 (Already a palindrome)

Input: s = "abracadabra"

Output: 4 (e.g., "a" | "b" | "r" | "aca" | "dabra" needs at least 4 cuts)

Code

public class Solution {
    public int minCut(String s) {
        int n = s.length();
        int[] dp = new int[n + 1];
        boolean[][] isPal = new boolean[n][n];
        for (int i = 0; i <= n; i++) dp[i] = i - 1; // Max cuts possible
        for (int i = 0; i < n; 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;
                    dp[i + 1] = Math.min(dp[i + 1], j == 0 ? 0 : dp[j] + 1);
                }
            }
        }
        return dp[n];
    }
}
            

def min_cut(s):
    n = len(s)
    dp = list(range(n + 1))  # dp[i] = min cuts for s[0:i]
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n):
        min_cuts = i  # Worst case: cut at every char
        for j in range(i + 1):
            if s[j] == s[i] and (i - j <= 2 or is_pal[j + 1][i - 1]):
                is_pal[j][i] = True
                min_cuts = min(min_cuts, 0 if j == 0 else dp[j] + 1)
        dp[i + 1] = min_cuts
    return dp[n]
            

function minCut(s) {
    let n = s.length;
    let dp = Array(n + 1).fill().map((_, i) => i - 1); // Max cuts
    let isPal = Array(n).fill().map(() => Array(n).fill(false));
    for (let i = 0; i < n; i++) {
        let minCuts = i;
        for (let j = 0; j <= i; j++) {
            if (s[j] === s[i] && (i - j <= 2 || isPal[j + 1][i - 1])) {
                isPal[j][i] = true;
                minCuts = Math.min(minCuts, j === 0 ? 0 : dp[j] + 1);
            }
        }
        dp[i + 1] = minCuts;
    }
    return dp[n];
}
            

Explanation

• DP Insight: dp[i] represents the minimum cuts needed for the substring s[0:i].
• Palindrome Check: Use a 2D table to mark palindromic substrings efficiently.
• Flow: For each position i, check all possible palindromic prefixes ending at i and minimize cuts based on prior results.
• Example Walkthrough: "aab" → dp[0]=-1, dp[1]=0 ("a"), dp[2]=0 ("aa"), dp[3]=1 ("aa"|"b").
• Optimization: Combines palindrome detection with DP to avoid redundant checks.

Note