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.

**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 minimum n-1 cut is needed.

**Example 1**

```
Input: S = "aba"
Output: 0
Explanation:"aba" is already a palindrome, so no cuts are needed.
```

**Example 2**

```
Input: S = "aab"
Output: 1
Explanation: Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
```

**Example 3**

```
Input: S = “ababbbabbababa”
Output: 3
Explanation: Here 3 cuts are needed.
The palindromes are: a | babbbab | b | ababa
```