Problem statement

Given a string s, partition it so that every part is a palindrome.

Return the minimum number of cuts needed.

Example 1

Input: s = "aab"
Output: 1
Explanation: One cut gives ["aa", "b"].

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.

Hints for Palindrome Partitioning II

1. Hint 1

   Precompute which substrings are palindromes before worrying about cuts.

2. Hint 2

   cuts[j] = minimum cuts for the prefix ending at j.

3. Hint 3

   If s[0..j] is itself a palindrome, cuts[j] is 0; otherwise try every palindromic suffix ending at j.

How to solve Palindrome Partitioning II

Two tables: one saying whether each substring is a palindrome, and one giving the minimum cuts per prefix. The second consults the first in O(1) per candidate split.

Approach

1. Build isPal[i][j] bottom-up: true when the endpoints match and the interior is a palindrome (or is shorter than two characters).
2. For each prefix end j: if s[0..j] is a palindrome, cuts[j] = 0.
3. Otherwise, over every i from 1 to j where s[i..j] is a palindrome, take min(cuts[i-1] + 1).
4. Return cuts[n-1].

Why it works

Any optimal partition of s[0..j] ends with some palindromic block s[i..j]. Splitting at its start reduces the problem to the already-solved prefix s[0..i-1] plus one cut, so the minimum over all valid i is exact.

Complexity

• Time — O(n²)
• Space — O(n²)

Pitfalls

• Re-checking palindromes inside the cut loop makes it O(n³) and times out at n = 2000.
• Initialising cuts[j] to j (cut everywhere) matters — it is the worst case and a valid upper bound.
• The answer counts cuts, not parts: a single palindrome needs 0.

Reference solution

Python

def minCut(s: str) -> int:
    n = len(s)
    if n == 0:
        return 0
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            if s[i] == s[j] and (j - i < 2 or is_pal[i + 1][j - 1]):
                is_pal[i][j] = True
    cuts = [0] * n
    for j in range(n):
        if is_pal[0][j]:
            cuts[j] = 0
            continue
        best = j
        for i in range(1, j + 1):
            if is_pal[i][j] and cuts[i - 1] + 1 < best:
                best = cuts[i - 1] + 1
        cuts[j] = best
    return cuts[n - 1]

Java

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

C++

int minCut(string s) {
    int n = (int) s.size();
    if (n == 0) return 0;
    vector<vector<char>> isPal(n, vector<char>(n, 0));
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            if (s[i] == s[j] && (j - i < 2 || isPal[i + 1][j - 1])) isPal[i][j] = 1;
        }
    }
    vector<int> cuts(n, 0);
    for (int j = 0; j < n; j++) {
        if (isPal[0][j]) { cuts[j] = 0; continue; }
        int best = j;
        for (int i = 1; i <= j; i++) {
            if (isPal[i][j] && cuts[i - 1] + 1 < best) best = cuts[i - 1] + 1;
        }
        cuts[j] = best;
    }
    return cuts[n - 1];
}

JavaScript

var minCut = function(s) {
    const n = s.length;
    if (n === 0) return 0;
    const isPal = [];
    for (let i = 0; i < n; i++) isPal.push(new Array(n).fill(false));
    for (let i = n - 1; i >= 0; i--) {
        for (let j = i; j < n; j++) {
            if (s.charAt(i) === s.charAt(j) && (j - i < 2 || isPal[i + 1][j - 1])) isPal[i][j] = true;
        }
    }
    const cuts = new Array(n).fill(0);
    for (let j = 0; j < n; j++) {
        if (isPal[0][j]) { cuts[j] = 0; continue; }
        let best = j;
        for (let i = 1; i <= j; i++) {
            if (isPal[i][j] && cuts[i - 1] + 1 < best) best = cuts[i - 1] + 1;
        }
        cuts[j] = best;
    }
    return cuts[n - 1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Prefix and Suffix Search Hard
• Recover a Tree From Preorder Traversal Hard
• Minimum Time to Revert Word to Initial State II Hard
• Maximum Product of the Length of Two Palindromic Substrings Hard
• Longest Chunked Palindrome Decomposition Hard
• K-Similar Strings Hard