A ceramic border is a string s of lowercase English letters, one letter per tile. You want to slice the border into contiguous pieces so that every piece reads the same forward and backward (a palindrome). A slice is a single cut between two adjacent tiles.
Determine the minimum number of cuts needed so that each resulting piece is a palindrome. A string that is already a palindrome needs 0 cuts.
A single line containing the string s (lowercase English letters only).
A single integer: the minimum number of cuts.
s <= 2000s contains only lowercase English letters (a-z).Example 1
Input
aab
Expected
1
Explanation
One cut between 'aa' and 'b' yields the palindromic pieces 'aa' and 'b', so the answer is 1.
Example 2
Input
racecar
Expected
0
Explanation
The whole string is already a palindrome, so no cuts are needed: 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →