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.