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