Palindrome Partitioning II
Hard · Dynamic Programming · String · Dynamic Programming
Problem
Given a string s, cut it into consecutive pieces so that every piece is a palindrome (it reads the same forward and backward).
Return the fewest cuts that make this possible. A string that is already a palindrome needs 0 cuts, and a string of n letters never needs more than n - 1, because a single letter is always a palindrome.
Examples
Input: s = "abccbad" Output: 1
One cut gives "abccba" | "d", and both pieces are palindromes.
Input: s = "pqr" Output: 2
No two neighboring letters match, so every letter becomes its own piece.
Input: s = "noon" Output: 0
The whole string is already a palindrome.
Constraints
- 1 <= len(s) <= 2000
- s consists of lowercase English letters
Approaches
- Prefix DP, check each last piece by reversing it — time O(n³), space O(n)
Follow-up
What if you must split into exactly k palindromes and may change letters to get there? Then each piece has a price (its mismatched mirror pairs) and the split becomes a DP over pieces: see the use case "Exactly k palindromes, fewest letter changes".
Related problems
Start free on Cariara · Coding problems · System design studio
