520. 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.

Constraints - `1 ≤ length of s ≤ 2000` - `s` contains only lowercase letters