Hard Problemspalindromepartitioninterval

Palindrome Partitioning

Given a string, split it into the fewest possible pieces such that every piece, read on its own, is a palindrome.

Example input

s = "abaabb"

Expected output

2 cuts, so 3 pieces

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i][j] is the fewest cuts that split the piece s[i..j], both ends included, into pieces that are all palindromes. The table counts cuts rather than pieces because a palindrome then costs 0 and the arithmetic stays a plain sum; the number of pieces is always the cuts plus 1, so the question as asked is answered by dp[0][n - 1] + 1. Two numbers name the state, where the piece starts and where it ends, so only the upper triangle, i <= j, means anything, and the answer for the whole string sits in the top-right corner.

dp[i][j] = 0 if s[i..j] is a palindrome, otherwise min over k from i to j - 1 of dp[i][k] + 1 + dp[k + 1][j]

First ask whether s[i..j] is already a palindrome. If it is, no cut can improve on leaving it whole, so the cell is 0, and that check is made on the string itself, comparing characters inward from both ends, not on the table. If it is not, at least one cut goes inside it, so ask where ONE of the cuts falls: after position k, for some k from i to j - 1. Everything left of that cut and everything right of it are then cut independently, and each side should use its own fewest cuts, because a side cut any worse could be swapped for its best without touching the other side. That costs dp[i][k] + 1 + dp[k + 1][j], and since you do not know which k the best cut set uses, try them all and keep the smallest. Taking the minimum over the choices for one decision is the move coin change makes, derived in its lesson at /courses/dynamic-programming/coin-change. It is also the same loop over split points the convolution1d pages run, nth-catalan-number among them: there every split is summed, because each one builds different trees, and here only the cheapest is kept.

dp[i][i] = 0 on the diagonal: one character is a palindrome. Any longer piece that is a palindrome, like 'aba' at dp[0][2] or 'baab' at dp[1][4], is also set to 0 without reading anything. Every other cell reads pairs: for a cut after position k, the piece to its left, dp[i][k], in its own row, and the piece to its right, dp[k + 1][j], in its own column, both strictly shorter than s[i..j]. Filling by length, every length-2 piece, then every length-3 piece, and so on, guarantees all of them are final first. On the grid that is a sweep along the diagonals, out to the top-right corner.

Tabulation over n(n + 1) / 2 pieces. A piece that is not a palindrome scans up to n - 1 cut positions, and the direct palindrome check costs up to n / 2 character comparisons, so the whole table is O(n³) time and O(n²) space. At 6 characters that is 21 cells: 6 bases and 15 computes, of which 4 are palindromes that read nothing and 11 scan their cuts, reading 56 values between them. Top-down memoization from dp[0][n - 1] saves nothing here: measured at every slider size, it visits all 21 pieces at 6 characters and every piece at every other size too, except at 3, where 'aba' is a palindrome and the recursion stops at the top. The variations below take the time down to O(n²).

Time O(n³)Space O(n²)

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[i][i] = 0 on the diagonal: one character is a palindrome. Any longer piece that is a palindrome, like 'aba' at dp[0][2] or 'baab' at dp[1][4], is also set to 0 without reading anything. Every other cell reads pairs: for a cut after position k, the piece to its left, dp[i][k], in its own row, and the piece to its right, dp[k + 1][j], in its own column, both strictly shorter than s[i..j]. Filling by length, every length-2 piece, then every length-3 piece, and so on, guarantees all of them are final first. On the grid that is a sweep along the diagonals, out to the top-right corner.

Rows ↓
Cols →

0 a

1 b

2 a

3 a

4 b

5 b

0 a

0

1

0

1

2

1 b

·

0

1

0

1

2 a

·

0

1

3 a

·

0

1

4 b

·

0

5 b

·

0

Rows ↓row i: where the piece of the string starts

Cols →column j: where it ends, so the cell is the fewest cuts that split s[i..j] into palindromes

palindrome-partitioning.ts

1function minPalindromeCuts(s) {
2 const n = s.length;
3 const isPal = (i, j) => {
4 while (i < j) if (s[i++] !== s[j--]) return false;
5 return true;
6 };
7 const dp = Array.from({ length: n }, () => new Array(n).fill(0));
8 for (let len = 2; len <= n; len++) {
9 for (let i = 0; i + len - 1 < n; i++) {
10 const j = i + len - 1;
11 if (isPal(i, j)) continue; // dp[i][j] stays 0: no cut needed
12 let best = Infinity;
13 for (let k = i; k < j; k++) {
14 best = Math.min(best, dp[i][k] + 1 + dp[k + 1][j]);
15 }
16 dp[i][j] = best;
17 }
18 }
19 return dp[0][n - 1];
20}

Base caseComputedBeing readAnswer

The code, the trap, the variations

palindrome-partitioning.ts

1function minPalindromeCuts(s) {
2 const n = s.length;
3 const isPal = (i, j) => {
4 while (i < j) if (s[i++] !== s[j--]) return false;
5 return true;
6 };
7 const dp = Array.from({ length: n }, () => new Array(n).fill(0));
8 for (let len = 2; len <= n; len++) {
9 for (let i = 0; i + len - 1 < n; i++) {
10 const j = i + len - 1;
11 if (isPal(i, j)) continue; // dp[i][j] stays 0: no cut needed
12 let best = Infinity;
13 for (let k = i; k < j; k++) {
14 best = Math.min(best, dp[i][k] + 1 + dp[k + 1][j]);
15 }
16 dp[i][j] = best;
17 }
18 }
19 return dp[0][n - 1];
20}

Where people go wrong

Cutting greedily: take the longest palindrome the string starts with, cut there, and repeat on the rest. It looks safe because a long palindrome swallows many characters at once, and on this page's string it is right at seven of the eight slider sizes, which is how it survives a few hand tests. At 5 characters it fails: on 'abaab' it takes 'aba', is left with 'ab', and ends at 'aba' | 'a' | 'b', 2 cuts, when 'a' | 'baab' needs 1. Taking a short first piece can open up a long palindrome behind it, and only trying every cut position sees that. The other slip is dropping the palindrome check and always minimising over cuts: then no piece longer than one character can ever cost 0, every cell comes out as its length minus 1, and at 6 characters the answer reads 5 instead of 2.

Look the palindrome check up in a table instead of comparing characters each time.
Build palindromic-substring-count's flag table first, O(n²) cells filled shortest stretch first, and each cell's check becomes a single lookup of flag[i][j] instead of up to n / 2 comparisons. The cut recurrence does not change at all, and neither does the O(n³) total, because the scan over cut positions inside every cell is still there. What it buys is that the expensive part is now only the scan, which the next variation removes.
Solve it over prefixes: cuts[j] is the fewest cuts for s[0..j].
The state loses a dimension. Every cut set has a LAST piece, so ask where it begins: if s[i..j] is a palindrome, the cuts are cuts[i - 1] + 1 (or 0 when i = 0, the whole prefix being one palindrome). So cuts[j] is the min of that over every i whose piece is a palindrome, read from the flag table. That is n cells with up to n choices each, O(n²) time, plus the O(n²) flag table. The answer does not change: on 'abaabb' the prefix row is 0, 1, 0, 1, 1, 2, ending at the same 2. What is lost is the answer for every inner piece, which the triangle has and this row never computes.
Return the pieces, not just how many cuts.
The table is unchanged; remember the winning k at each cell and walk down from dp[0][n - 1], splitting at k and recursing into both sides until each side is a palindrome. At 6 characters the first winners give 'a' | 'baab' | 'b'. Four cut positions tie at the top, so the walk is not the only answer: 'aba' | 'a' | 'bb' is also two cuts, and a different tie-break prints it instead.

Egg Dropping Problem Palindromic Substring Count