Palindrome Partitioning II: Minimum Cuts with DP

Given a string s, return the minimum number of cuts needed so that every substring of the partition is a palindrome. For example, "aab" needs 1 cut (["aa", "b"]), "a" needs 0 cuts, and "ab" needs 1 cut (["a", "b"]).

This is LeetCode 132: Palindrome Partitioning II, a hard problem. Where the original Palindrome Partitioning asks you to list all valid partitions, this variant asks for just the minimum cut count, which turns it into a pure DP optimization problem.

Why brute force fails

You could generate every possible partition of the string, check whether all pieces are palindromes, and track the one with the fewest cuts. The number of ways to partition a string of length n is 2^(n-1) (each gap between characters is either a cut or not), and checking palindromes takes O(n) per partition. That is O(n * 2^n), which is far too slow for n up to 2000.

Even the backtracking approach from Palindrome Partitioning I will time out here. You need a way to avoid re-examining the same subproblems.

The approach: two-phase DP

The solution splits into two clean phases.

Phase 1: precompute the palindrome table

Build a 2D boolean table is_pal[i][j] that tells you whether s[i..j] is a palindrome. You can fill this using the classic expand-from-center idea or by iterating on substring length:

• Every single character is a palindrome: is_pal[i][i] = True.
• Two characters are a palindrome if they match: is_pal[i][i+1] = (s[i] == s[i+1]).
• For longer substrings: is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1].

This runs in O(n^2) time and space.

Phase 2: minimum-cut DP

Define dp[i] as the minimum number of cuts needed for s[0..i]. You want dp[n-1].

For each position i, try every possible last palindrome s[j..i]:

• If is_pal[j][i] is true and j == 0, then the entire prefix s[0..i] is a palindrome. No cuts needed: dp[i] = 0.
• If is_pal[j][i] is true and j > 0, then you can place a cut before position j and use the best result for the prefix: dp[i] = min(dp[i], dp[j-1] + 1).

Initialize dp[i] = i (worst case: cut between every character, producing i cuts for a prefix of length i+1).

Walking through the example

Let's trace s = "aab" step by step through both phases.

The final answer is dp[2] = 1. One cut produces ["aa", "b"], both palindromes.

The code

def min_cut(s):
    n = len(s)
    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

    dp = list(range(n))
    for i in range(1, n):
        if is_pal[0][i]:
            dp[i] = 0
            continue
        for j in range(1, i + 1):
            if is_pal[j][i]:
                dp[i] = min(dp[i], dp[j - 1] + 1)

    return dp[n - 1]

The palindrome table fills from the bottom-right corner, ensuring that is_pal[i+1][j-1] is already computed when you need it. The DP array scans left to right, looking back at all valid palindrome endings.

Complexity analysis

Time: O(n^2). Phase 1 fills an n-by-n table with O(1) work per cell. Phase 2 iterates over all pairs (i, j) where j goes from 0 to i, which is also O(n^2) total.

Space: O(n^2). The is_pal table dominates. The dp array is O(n).

Edge cases to watch for

Before submitting, make sure your solution handles these:

• Already a palindrome like "aba" or "aaa": the entire string needs 0 cuts. The is_pal[0][n-1] check catches this immediately.
• All different characters like "abcd": every character must be its own partition, giving n - 1 cuts. The worst-case initialization dp[i] = i covers this.
• Single character like "a": trivially a palindrome, 0 cuts. dp[0] = 0.
• Two identical characters like "aa": palindrome, 0 cuts.
• Two different characters like "ab": not a palindrome, 1 cut.

The building blocks

This problem is built on two reusable patterns:

Palindrome precomputation. The is_pal[i][j] table is the same structure used in Longest Palindromic Substring and Palindromic Substrings. You expand from the base cases (length 1 and 2) outward, relying on the recurrence is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]. Once you have this table, any palindrome query is O(1). This pattern shows up whenever a problem needs to know which substrings are palindromes.

Prefix-cut DP. The dp[i] = min cuts for s[0..i] formulation is a classic "optimal partition" pattern. You scan left to right, and for each position you look back at all valid split points. The same structure appears in Word Break (can you partition into dictionary words?) and other string partitioning problems. The key insight is that you reduce a partitioning problem to a 1D DP by fixing the right endpoint and iterating over left endpoints.

Once you internalize these two patterns, the two-phase structure of this solution becomes natural. Phase 1 gives you O(1) palindrome lookups. Phase 2 uses those lookups in a standard prefix DP.

From understanding to recall

Reading through this solution and nodding along is the easy part. The hard part is reproducing it under pressure, from scratch, without looking at a reference. Can you write the palindrome table fill order? Do you remember the DP recurrence? Do you handle the j == 0 case correctly?

Spaced repetition closes that gap. Instead of solving this problem once and forgetting the details in a week, you revisit the core patterns at increasing intervals. Each time you write both phases from memory. After a few repetitions, it is automatic.

The palindrome precomputation and prefix-cut DP are two of roughly 60 reusable building blocks that appear across hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding through problems and hoping they stick.

Related posts

• Palindrome Partitioning - The backtracking variant that lists all valid palindrome partitions
• Longest Palindromic Substring - Uses the same palindrome precomputation table to find the longest single palindrome