Given a string, a partitioning of the string is a palindrome partitioning if every substring of the partition is a palindrome.

For example, $aba|b|bbabb|a|b|aba$ is a palindrome partitioning of $ababbbabbababa.$

Determine the fewest cuts needed for a palindrome partitioning of a given string. For example, minimum of $3$ cuts are needed for $ababbbabbababa.$ The three cuts are $a|babbbab|b|ababa.$ If a string is a palindrome, then minimum $0$ cuts are needed.

If a string of length $n$ contains all different characters, then minimum $n$-$1$ cuts are needed.