132. Palindrome Partitioning II
You are given a lowercase string s. It must be sliced into contiguous pieces so that every piece is a palindrome, and you want to make as few cuts as possible. Return that minimum number of cuts.
A string that is already a palindrome needs 0 cuts, and cutting between every pair of letters (n - 1 cuts) always works — the answer lives somewhere between those two extremes.
Unlike the enumeration version of this problem, you are not asked for the partitions themselves — only the count of cuts in the best one.
Example 1:
Input: s = "aab"
Output: 1
Explanation: One cut after "aa" leaves the palindromic pieces "aa" and "b". No zero-cut answer exists because "aab" itself is not a palindrome.
Example 2:
Input: s = "noon"
Output: 0
Explanation: "noon" already reads the same in both directions, so no cut is needed.
Example 3:
Input: s = "abcde"
Output: 4
Explanation: No two adjacent letters match anywhere, so the only palindromic pieces are single letters — 4 cuts.
Constraints:
- 1 ≤ s.length ≤ 1000
- s consists of lowercase English letters.
Hints:
Enumerating all partitions (like Palindrome Partitioning I) is exponential and hopeless at n = 1000. When only the best score is wanted, think dynamic programming over prefixes: let best[i] be the fewest cuts for the first i + 1 characters.
best[i] = 0 when s[0..i] is a palindrome; otherwise it is 1 + min(best[j-1]) over every j where s[j..i] is a palindrome. Answering "is s[j..i] a palindrome?" in O(1) needs the precomputed table pal[i][j] = (s[i] == s[j] and pal[i+1][j-1]).
To shrink space to O(n), flip the direction of discovery: expand outward from every center (odd and even). Each time the palindrome s[l..r] is confirmed, relax cuts[r + 1] with cuts[l] + 1 — every palindrome is found exactly at its center, so nothing is missed.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "aab"
Expected output: 1