Palindrome Partitioning II
Find the minimum number of cuts that split a string into palindromes, with a dynamic program over prefixes and a palindrome table filled along the way.
Problem Understanding
Palindrome Partitioning II: partition s so that every piece is a palindrome, using as few cuts as possible. Return that minimum number of cuts.
Examples: "aab" → 1 ("aa" | "b"); "a" → 0; "ab" → 1.
The Intuition: Decide the Last Piece
The best split of a prefix ends with some palindrome. Try them all:
- cuts[i] = fewest cuts for
s[0..i]. - For each palindromic last piece
s[j..i]: the prefix before it costscuts[j − 1], plus one cut. - If the whole prefix is a palindrome, it costs 0.
The palindrome checks reuse smaller answers like Palindromic Substrings, and the "best split of a prefix" structure is the one in Word Break.
Interactive Walkthrough
MARKED = LAST PIECE s[j..i] · TINTED = THE PREFIX BEFORE IT
cuts[i] ≤ i
s
cuts
i
:
cuts[i]
:
answer
:
cuts[i] = fewest cuts for s[0..i]. A string of length 6 never needs more than 5
Next
"a" is a palindrome from the start: s[0..0] needs 0 cuts
s
The candidate last piece s[j..i] is marked (red when it is not a palindrome) and the prefix before it is tinted. The cuts row fills in left to right. Try All different for the worst case.
Dry Run Table
Input: "abacdc".
| i | Prefix | Best last piece | cuts[i] |
|---|---|---|---|
| 0 | a | a | 0 |
| 1 | ab | b | 1 |
| 2 | aba | aba (whole) | 0 |
| 3 | abac | c | 1 |
| 4 | abacd | d | 2 |
| 5 | abacdc | cdc | 1 |
Answer: 1 ("aba" | "cdc").
The Solution Template
One double loop fills the palindrome table and the cuts together.
Palindrome Partitioning II Code
1var minCut = function(s) {2 const n = s.length;3 const pal = Array.from({ length: n }, () => new Array(n).fill(false));4 const cuts = new Array(n);5 for (let i = 0; i < n; i++) {6 cuts[i] = i;7 for (let j = 0; j <= i; j++) {8 if (s[j] === s[i] && (i - j <= 1 || pal[j + 1][i - 1])) {9 pal[j][i] = true;10 if (j === 0) cuts[i] = 0;11 else cuts[i] = Math.min(cuts[i], cuts[j - 1] + 1);12 }13 }14 }15 return cuts[n - 1];16};
Edge Cases & Common Mistakes
- Whole string is a palindrome: 0 cuts.
- All characters different: n − 1 cuts.
- Checking palindromes from scratch each time: O(n³); use the table.
- Cuts vs pieces: pieces = cuts + 1; return cuts.
- Backtracking all partitions: correct but exponential.
Summary
cuts[i] is the minimum over palindromic last pieces s[j..i] of cuts[j − 1] + 1 (0 if j = 0), with palindromes found from smaller ones as you go. O(n²) time and space.
More practice: DSA interview questions with answers · patterns cheat sheet