Fewest Palindrome Cuts

A palindrome reads the same forwards and backwards, like "noon" or "x". Write min_cuts(s) that returns the fewest cuts needed to split the string s into consecutive pieces that are all palindromes. A string that is already a palindrome needs 0 cuts.

Examples

min_cuts("banana")  # returns 1
min_cuts("abcbm")   # returns 2
min_cuts("level")   # returns 0

"banana" splits as "b" and "anana", and "abcbm" as "a", "bcb" and "m".

Constraints

• 1 <= len(s) <= 600
• s holds lowercase letters only.