Palindrome Partitioning II
Hard· palindrome DP· partition DP
Problem
Cut a string into pieces so that every piece is a palindrome. Return the minimum number of cuts needed.
Examples
Input: s = "aab"
Output: 1
"aa" | "b".
Input: s = "abccbd"
Output: 2
"a" | "bccb" | "d".
Constraints
- • 1 <= s.length <= 2000
- • Only lowercase English letters
Hints & approach
Hint 1
Precompute which substrings are palindromes so each check is O(1).
Hint 2
Let cuts[i] be the minimum cuts for the first i characters.
Hint 3
cuts[i] = min over j where s[j..i) is a palindrome of cuts[j] + 1.
Approachtry the hints first
First build isPal[j][i] with the palindromic DP: s[j..i] is a palindrome if its ends match and the inside is a palindrome (or has length ≤ 2). Then let cuts[i] be the minimum cuts for the prefix of length i, with cuts[0] = -1 so a whole-palindrome prefix costs 0. For each i, try every j where s[j..i) is a palindrome and take cuts[j] + 1. Expanding around each centre can replace the table to save memory.
Time O(n²) · Space O(n²)