LeetCode #132 Hard

Palindrome Partitioning II

Minimum cuts so every piece of string s is a palindrome.

dpstringpalindrome

02

Intuition

💡

Two DP layers. First, precompute pal[i][j] — is s[i..j] a palindrome? — by expanding shorter spans into longer ones (ends match + inside is a palindrome). Then cuts[i] = fewest cuts for the prefix ending at i: for every j where s[j..i] is a palindrome, the prefix before j plus one cut is a candidate; a palindromic full prefix needs zero.

03

Approach

1

Palindrome table first

pal[i][j] = (s[i]==s[j]) and (j−i < 2 or pal[i+1][j−1]). Filling by increasing length makes the inner lookup already available. O(n²) time and space.

2

Cuts DP on top

cuts[i] = 0 if s[0..i] is a palindrome, else min over all palindromic suffixes s[j..i] of cuts[j−1] + 1. Enumerating only palindromic last pieces is what the table enables in O(1) per check.

3

Why not backtracking

Enumerating all partitions (problem 131) is exponential; here only the count of cuts matters, so per-prefix minima collapse the search to O(n²).

04

Solution & live demo

python

▶1class Solution:
▶2    def minCut(self, s):
▶3        n = len(s)
▶4        pal = [[False] * n for _ in range(n)]
▶5        for length in range(1, n + 1):
▶6            for i in range(n - length + 1):
▶7                j = i + length - 1
▶8                pal[i][j] = s[i] == s[j] and (j - i < 2 or pal[i+1][j-1])
▶9        cuts = [0] * n
▶10        for i in range(n):
▶11            if pal[0][i]:
▶12                cuts[i] = 0
▶13                continue
▶14            cuts[i] = min(cuts[j-1] + 1 for j in range(1, i + 1) if pal[j][i])
▶15        return cuts[-1]

05

Edge cases

Already a palindrome

cuts[n−1] = 0 via the full-prefix check.

All distinct characters

Only single chars are palindromes — n−1 cuts.

Single character

0 cuts.

06

Complexity

Time

O(n²)

Space

O(n²)

Both the palindrome table and the cuts DP are quadratic.