Palindrome Partitioning II

HardString DP · Palindrome Table / Centre Expansion🧩 String DP LeetCode #132 ↗Updated Oct 30, 2026

Problem

Split the string s into consecutive pieces so that every piece is a palindrome. Return the smallest number of cuts that makes this possible (a string that is already a palindrome needs 0 cuts).

Inputs = "aab"Output1 ("aa" | "b")

Inputs = "a"Output0

Inputs = "ab"Output1

1 ≤ s.length ≤ 2000 · lowercase English letters

Try it yourself

Java

class Solution {
    public int minCut(String s) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Let cut[k] be the best answer for the first k characters. Any palindrome s[l..r] gives cut[r+1] ≤ cut[l] + 1. Generating every palindrome by expanding around centres relaxes all these edges with no n×n table.

PatternString DP

Instinct Two strings compared char by char (match, edit, interleave) means dp[i][j] over prefixes; one string's palindromes or splits means dp[l][r] or dp[i].

Memory hack Match? Go diagonal. Mismatch? Ask the neighbours. Up drops a char from s, left drops one from t, diagonal uses both.

Open the String DP guide →

Approaches

Brute ForceRecursion over Palindromic Prefixes

Time O(n·2ⁿ)Space O(n)

parts(start) = fewest palindromic pieces covering s[start..]: try every end where s[start..end] is a palindrome and recurse on the rest. Cuts = pieces − 1.

Java

public int minCut(String s) {
    return parts(s, 0) - 1;
}

private int parts(String s, int start) {
    if (start == s.length()) return 0;
    int best = Integer.MAX_VALUE;
    for (int end = start; end < s.length(); end++) {
        if (isPalindrome(s, start, end)) best = Math.min(best, 1 + parts(s, end + 1));
    }
    return best;
}

private boolean isPalindrome(String s, int l, int r) {
    while (l < r) {
        if (s.charAt(l++) != s.charAt(r--)) return false;
    }
    return true;
}

Explores every partition; fine for tiny strings, hopeless at n = 2000.

BetterPalindrome Table + 1-D Cut DP

Time O(n²)Space O(n²)

Sweep the right end j. For each start i ≤ j, decide pal[i][j] in O(1) from pal[i+1][j-1] (already filled for column j-1). If it is a palindrome, the last piece can be s[i..j]: that needs 0 cuts when i = 0, else cuts[i-1] + 1.

Java

public int minCut(String s) {
    int n = s.length();
    boolean[][] pal = new boolean[n][n];
    int[] cuts = new int[n]; // cuts[j] = min cuts for s[0..j]
    for (int j = 0; j < n; j++) {
        int best = j; // worst case: cut between every char
        for (int i = 0; i <= j; i++) {
            if (s.charAt(i) == s.charAt(j) && (j - i < 2 || pal[i + 1][j - 1])) {
                pal[i][j] = true;
                best = (i == 0) ? 0 : Math.min(best, cuts[i - 1] + 1);
            }
        }
        cuts[j] = best;
    }
    return cuts[n - 1];
}

Quadratic time, but the boolean table is 4 million cells at n = 2000.

OptimalCentre Expansion Relaxing a Cut Array

Time O(n²)Space O(n)

Use cut[k] for the prefix of length k, with cut[0] = -1 so a whole-prefix palindrome costs -1 + 1 = 0. Expand around each centre in increasing order; every palindrome s[l..r] found updates cut[r+1] from cut[l]. Since l is at most the centre, cut[l] is already final when it is read.

Java

public int minCut(String s) {
    int n = s.length();
    int[] cut = new int[n + 1]; // cut[k] = min cuts for the first k chars
    for (int k = 0; k <= n; k++) cut[k] = k - 1;
    for (int c = 0; c < n; c++) {
        relax(s, cut, c, c);     // odd-length palindromes
        relax(s, cut, c, c + 1); // even-length palindromes
    }
    return cut[n];
}

private void relax(String s, int[] cut, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
        cut[r + 1] = Math.min(cut[r + 1], cut[l] + 1);
        l--;
        r++;
    }
}

Dry runs = "aab"

changed

init
-1

0

1

2

cut[k] = k-1
c=0 odd
-1

0

1

2

"a": cut[1]=0
c=0 even
-1

0

0

2

"aa": cut[2]=0
c=1
-1

0

0

2

"a": 0 stays; ab ✘
c=2 odd
-1

0

0

1

"b": cut[3]=0+1=1 ✔

Same quadratic time with only an O(n) array — no palindrome table at all.

Pro tip

The cut[0] = -1 sentinel removes the special case for palindromic prefixes — call it out when you write the init loop.

At a glance

Level	Approach	Time	Space
Brute Force	Recursion over Palindromic Prefixes	`O(n·2ⁿ)`	`O(n)`
Better	Palindrome Table + 1-D Cut DP	`O(n²)`	`O(n²)`
Optimal	Centre Expansion Relaxing a Cut Array	`O(n²)`	`O(n)`

Common pitfalls

Returning the number of pieces instead of cuts — off by one.
Greedily taking the longest palindromic prefix — "aaba"-style inputs break it.
Building the full table and running Palindrome Partitioning I's backtracking — exponential.

Interview tips

Separate the two sub-problems: is s[i..j] a palindrome? and min cuts for a prefix.
Explain why cut[l] is final when read: every palindrome ending before l was already seen.
Mention the table's memory (n² booleans) as the motivation for centre expansion.

Pattern

Prefix DP + palindrome oracle → minimise pieces when each piece must satisfy a substring property.

My notes saved in this browser