Palindromic Partitioning

Palindromic partitioning works by cutting a string into segments where every segment reads the same forwards and backwards, and it finds the minimum number of cuts by combining two smaller decisions — "is s[i..j] a palindrome?" and "what is the fewest cuts for the prefix ending at i?" — into one bottom-up table, so overlapping sub-answers are computed once instead of exponentially many times.

Recognize the pattern

• The task asks for a minimum/maximum count of ways to split a sequence into valid contiguous pieces (here, palindromes).
• Validity of a piece depends only on its own characters (palindrome check), not on neighboring pieces.
• Small input bound (n ≤ 16 in the source constraints) is a hint that an O(n²) DP with an O(n²) palindrome table is intended.
• Any "partition string into parts satisfying property P, minimize/count partitions" problem (word break, partition into k palindromic substrings) shares this shape: precompute P over all substrings, then DP over cut positions.

Brute force → optimal

Brute force: try every subset of cut positions (2^(n-1) ways to place cuts between n-1 gaps), check whether every resulting piece is a palindrome, keep the split with fewest cuts. Cost: exponential in n, plus O(n) per palindrome check per piece — roughly O(2^n · n).

Optimal (DP): first build isPal[i][j] for all substrings in O(n²) time using isPal[i][j] = s[i]==s[j] && (j-i<2 || isPal[i+1][j-1]). Then define cuts[i] = minimum cuts needed for prefix s[0..i]. For each i, scan every j ≤ i where s[j..i] is a palindrome and take cuts[i] = min(cuts[i], j==0 ? 0 : cuts[j-1]+1). This replaces exponential search with O(n²) time.

Complexity, derived

isPal table: n² substrings, each check is O(1) once shorter palindromes are known (fill by increasing length) → O(n²) time, O(n²) space.

cuts array: outer loop over i (n values) × inner loop over j ≤ i (up to n values) = O(n²) operations, each O(1). Total time O(n²), space O(n²) for the palindrome table plus O(n) for cuts — dominated by O(n²).

Compare to brute force's O(2^n · n): for n=16, cuts are placed in 2^(16-1) = 2^15 = 32,768 ways, so brute force does roughly 32,768 × 16 ≈ 524,288 checks versus the DP's 16² = 256 operations — a gap that only grows with n.

Worked example: "cddpd"

Indices 0..4 = c,d,d,p,d. Build isPal (only palindromic spans shown, plus the two lookups needed later): [0,0]="c" ✓, [1,1]="d" ✓, [1,2]="dd" ✓, [2,4]="dpd" ✓ (d==d, middle p trivially palindrome), all single chars ✓. Among the non-palindromic spans, note the two that the cuts[4] derivation below relies on: isPal[2][3]="dp" ✗ (d≠p) and isPal[1][4]="ddpd" ✗ (d==d at the ends, but the inner span isPal[2][3]="dp" is false, so the whole span fails). Other spans such as [0,4]="cddpd" are also ✗.

Result: 2 cuts, matching pieces "c", "d", "dpd".

Code

Assumes non-empty input (see pitfalls below for the empty-string edge case).

class Solution {
    public int minCut(String s) {
        int n = s.length();
        boolean[][] isPal = new boolean[n][n];
        for (int i = 0; i < n; i++) isPal[i][i] = true;
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j) && (len == 2 || isPal[i + 1][j - 1])) {
                    isPal[i][j] = true;
                }
            }
        }
        int[] cuts = new int[n];
        for (int i = 0; i < n; i++) {
            if (isPal[0][i]) { cuts[i] = 0; continue; }
            cuts[i] = Integer.MAX_VALUE;
            for (int j = 1; j <= i; j++) {
                if (isPal[j][i] && cuts[j - 1] + 1 < cuts[i]) {
                    cuts[i] = cuts[j - 1] + 1;
                }
            }
        }
        return cuts[n - 1];
    }
}

Pitfalls

• Checking palindromes with a fresh O(n) scan inside the DP loop turns O(n²) into O(n³) — always precompute isPal by increasing length first.
• When len == 2 the code deliberately skips reading isPal[i+1][j-1] (that would be a length-0 span, i.e. i+1 > j-1) and short-circuits on s.charAt(i)==s.charAt(j) alone; if you instead always evaluate isPal[i+1][j-1] without that guard, you read an uninitialized (default-false) cell and every 2-character palindrome like "dd" is wrongly marked false, cascading into wrong cuts counts.
• Empty input: n = s.length() == 0 makes the final cuts[n - 1] read cuts[-1], throwing ArrayIndexOutOfBoundsException. The code above assumes n ≥ 1; guard with an explicit if (n == 0) return 0; (or equivalent) before building the tables if empty strings are a valid input.
• Forgetting the isPal[0][i] shortcut means cuts[i] never reaches 0 even when the whole prefix is already a palindrome.
• Confusing "number of cuts" with "number of pieces" (cuts = pieces − 1) is a common off-by-one in the final answer.

When to use / when not — trade-offs

Use this DP when you need the exact minimum cuts and n is small-to-moderate (up to a few thousand, since O(n²) space/time is the ceiling). It beats brute force by pruning shared substring work into a lookup table.

vs. Manacher's algorithm: Manacher finds all palindromic substrings/centers in O(n) but does not by itself solve the partition-minimization problem — it only accelerates building isPal implicitly; you'd still need the O(n²) or better cuts DP on top, so it helps when n is large and the O(n²) isPal table is the bottleneck, not the cuts recurrence.

vs. counting all partitions (backtracking with memoization): if the problem asks to enumerate every valid partition rather than just the minimum cut count, DP alone won't suffice — you need backtracking, optionally pruned by the same isPal table for speed.

Takeaways

• Precompute substring validity once (O(n²)), then DP over cut positions using that table — never recompute validity inside the cut loop.
• The pattern generalizes to any "minimum partitions satisfying property P" problem.
• Time and space are both O(n²), driven by the isPal table, not the cuts array.
• Guard the empty-string edge case explicitly — the natural implementation indexes cuts[n-1] and breaks at n=0.
• The extremes anchor the answer range: an already-palindromic string needs 0 cuts; a string of all-distinct characters needs n−1 cuts (every character its own piece); e.g. "aab" → 1 cut ("aa"|"b").

Recall: Why does precomputing isPal[i][j] by increasing substring length (not by increasing i) matter for correctness?

Source: adapted and deepened from the study guide's Palindromic Partitioning page (DSA / Dynamic Programming), cross-checked against standard interval-DP treatments of palindrome partitioning (e.g. LeetCode 132 Palindrome Partitioning II).