Given string
str
, write a program to partition
str
such that every substring of the partition is a palindrome. Return the
minimum cuts needed for a palindrome partitioning
of
str
.
Problem Note
- If a string is a palindrome, then minimum 0 cuts are needed.
-
If a string of length
n
containing all different characters, then the minimumn-1
cut is needed.
Example 1
Input: str = "aba"
Output: 0
Explanation:"aba" is already a palindrome, so no cuts are needed.
Example 2
Input: str = "aab"
Output: 1
Explanation: Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
Example 3
Input: str = “ababbbabbababa”
Output: 3
Explanation: Here 3 cuts are needed.
The palindromes are: a | babbbab | b | ababa