Palindrome Partitioning — Minimum Cuts
mediumDynamic Programming II+20 XPTime limit 3s
Cut a word into pieces so that every piece is a palindrome. What is the minimum number of cuts needed? (A single letter is always a palindrome, so n − 1 cuts always work.)
Input: one line with the word.
Output: the minimum number of cuts.
Constraints: 1 ≤ length ≤ 1500; lowercase letters.
Example: aab → aa | b, 1 cut. abacdc → aba | cdc, 1 cut.
Think about it: cuts[i] = minimum cuts for the first i letters. If s[j..i−1] is a palindrome, cuts[i] can be cuts[j] + 1. Checking palindromes naively makes this O(n³); precompute them (a isPal[j][i] table) or expand around every centre to get O(n²).
Sample input 1
aab
Sample output 1
1
Sample input 2
abacdc
Sample output 2
1
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).