Fewest Palindrome Cuts
Split S into the minimum number of contiguous pieces, each a palindrome. Print the minimum number of CUTS (pieces − 1).
Input: one line with the string S.
Output: the minimum number of cuts.
Constraints:
- 1 ≤ |S| ≤ 2000
- lowercase letters
Sample Tests
Input 1
aab
Output 1
1
Input 2
abc
Output 2
2
Discussion (opens after you solve — no spoilers before)
No comments yet.