Loading...
Loading...
Loading...
A word is cut into pieces by straight cuts between letters. Every piece must read the same backwards and forwards. Print the smallest number of cuts needed. A word that is already a palindrome needs 0 cuts.
Example 1
Input
aab
Output
1
Cut once into aa and b.
Example 2
Input
abcba
Output
0
Try the problem first. Open one hint at a time.
First build a table that says whether each range is a palindrome, filled by length.
Then let cuts[j] be the best for the first j + 1 letters: 0 if they are a palindrome, otherwise the best over every palindromic last piece.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor