Palindrome Partitioning II
Palindrome Partitioning II: minimum cuts so every piece of string s is a palindrome.
- 1 <= s.length <= 2000
- s consists of lowercase English letters only.
Intuition
Palindrome partitioning ii asks for the minimum number of cuts so every piece is a palindrome. The difference from Palindrome Partitioning I matters: that problem enumerates all partitions and is exponential, while this one asks only for a count, and counts collapse.
The solution is two DP layers stacked, and separating them is what makes it manageable.
First, precompute which substrings are palindromes. A substring is a palindrome when its two ends match and its interior is a palindrome — a recurrence on span length, filled from short spans outward so the interior is always known:
- pal[i][j] = (s[i] == s[j]) and (j − i < 2 or pal[i+1][j−1])
That table costs O(n²) and turns every later palindrome question into an O(1) lookup.
Second, the cuts themselves. Let cuts[i] be the fewest cuts needed for the prefix ending at i. To compute it, consider every position j where s[j..i] is a palindrome — that piece can be the last one. The cost is then cuts[j−1] + 1.
The base case carries real weight: if s[0..i] is itself a palindrome, zero cuts are needed and no minimum is taken. Missing that case makes every answer one too large.
Enumerating only palindromic last pieces, at O(1) per check thanks to the first table, is what brings the whole thing to O(n²) instead of exponential.
Two DP tables stacked: first precompute which substrings are palindromes, then compute minimum cuts using that lookup. Doing it in one pass would re-test the same substrings repeatedly. Building an O(n²) fact table so the second phase can query it in O(1) is a pattern worth naming — it's the same trick behind many interval DPs.
Approach
Before reading on: price up what the direct approach costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(n²) time and O(n²) space.
Build the palindrome table first
pal[i][j] is true when s[i..j] reads the same both ways. Fill by increasing span length so the interior pal[i+1][j-1] is already known when needed. This one-time O(n²) cost makes every later check O(1).
Handle short spans in the same condition
A span of one or two characters has no interior to check, so j - i < 2 short-circuits the recurrence. Folding it into the same expression avoids separate base-case loops and the off-by-one errors they invite.
Define cuts over prefixes
cuts[i] is the minimum number of cuts for s[0..i]. Indexing by prefix end is what makes the state one-dimensional — the second dimension is already absorbed by the palindrome table.
Set zero cuts for a palindromic prefix
If s[0..i] is itself a palindrome, cuts[i] = 0 with no minimum taken. Omitting this base case inflates every answer by one, and it is the most common bug in this problem.
Minimise over palindromic last pieces
Otherwise, for every j from 1 to i where s[j..i] is a palindrome, take cuts[j-1] + 1 and keep the smallest. Only palindromic suffixes are considered, which the table makes cheap to test.
Contrast with Palindrome Partitioning I
Problem 131 enumerates every valid partition and is inherently exponential in the output size. Here only a count is needed, so per-prefix minima collapse the search to O(n²) — a good example of how the question asked changes the achievable complexity.
Cost of the two tables
The palindrome table is O(n²) in time and space, and the cuts DP is O(n²) time with O(n) space. Total O(n²), which is fine for the n ≤ 2000 constraint.
Solution & live demo
Common pitfalls
Testing palindromes by slicing inside the cut loop
if s[j:i+1] == s[j:i+1][::-1]:
pal[i][j] = s[i] == s[j] and (j - i < 2 or pal[i+1][j-1])
Each slice-and-reverse is O(n), making the whole solution O(n³) and timing out. The table computes each fact once by reusing the shorter palindrome inside it.
Filling the palindrome table in index order
for i in range(n):
for j in range(i, n):
pal[i][j] = s[i] == s[j] and pal[i+1][j-1]for length in range(1, n + 1):
for i in range(n - length + 1):
j = i + length - 1pal[i+1][j-1] describes a shorter substring, so all shorter lengths must already be computed. Iterating by length guarantees that; iterating by start index reads cells that are still empty.
Not special-casing a whole-prefix palindrome
cuts[i] = min(cuts[j-1] + 1 for j in range(1, i + 1) if pal[j][i])
if pal[0][i]:
cuts[i] = 0
continueIf the entire prefix is already a palindrome the answer is zero cuts, but the comprehension always adds at least one. It can also be empty — raising a ValueError on min — when no valid split exists.
Edge cases
cuts[n−1] = 0 via the full-prefix check.
Only single chars are palindromes — n−1 cuts.
0 cuts.