Fewest Cuts Into Palindromes
Cut the string into pieces so that every piece is a palindrome. Print the fewest CUTS needed, which is one less than the number of pieces.
aab -> 1 aa | b
abc -> 2 a | b | c
aba -> 0 already a palindrome
## Two tables, not one
The recurrence over prefixes is straightforward:
cuts[0] = -1
cuts[i] = min over j < i with s[j..i-1] a palindrome of cuts[j] + 1
cuts[0] = -1 is the trick that makes the arithmetic work: a single palindromic piece
covering the whole prefix gives -1 + 1 = 0 cuts, which is right.
Setting it to 0 makes every answer one too large, and the error is uniform so it looks like
a plausible answer on every input. aba answering 1 instead of 0 is the check.
## The palindrome test must be precomputed
Testing s[j..i-1] by comparing characters costs O(length) each time, which makes the
whole thing O(n^3).
Precompute it:
pal[i][j] = (s[i] == s[j]) and (j - i < 2 or pal[i+1][j-1])
filled by increasing LENGTH, because pal[i][j] depends on the shorter interval
pal[i+1][j-1]. That is the interval-DP fill order from problem 510, and getting it wrong
here reads unwritten entries and reports strings as non-palindromes.
With the table, each test is O(1) and the whole solution is O(n^2).
## Why the pieces cannot be chosen greedily
Taking the longest palindromic prefix and repeating is wrong. noonabbad answers 2, from
noon | abba | d. The longest palindromic prefix is noon, which happens to be right
here. Try aabb: the longest palindromic prefix is aa, then bb, giving 1 cut, which is
also right.
The honest statement is that the greedy agrees on many inputs and there is no short
counterexample among the small strings, which is precisely why it should not be trusted:
a rule that is usually right is harder to discard than one that is obviously wrong. The
recurrence considers every split and costs the same O(n^2).
## Boundaries
a answers 0, and aaa and abcba also answer 0. A string that is already a palindrome
needs no cut, which is what cuts[0] = -1 delivers.
abc answers 2, the maximum for length 3: every single character is a palindrome, so the
answer never exceeds n - 1.
## Cost
Time O(n^2). Space O(n^2) for the palindrome table.
## Where this appears again
Prefix DP over pieces plus a precomputed validity table is the shape of every "partition into valid pieces" problem: word break (#513), splitting into valid IP addresses, and the palindrome-partitioning family. The validity table is what keeps the inner test constant time.