# Palindrome Partitioning ll

Posted: 11 Nov, 2020

Difficulty: Hard

#### Given a string ‘str’. Find the minimum number of partitions to make in the string such that every partition of the string is a palindrome.

#### Given a string, make cuts in that string to make partitions containing substrings with size at least 1, and also each partition is a palindrome. For example, consider “AACCB” we can make a valid partition like A | A | CC | B. Among all such valid partitions, return the minimum number of cuts to be made such that the resulting substrings in the partitions are palindromes.

#### The minimum number of cuts for the above example will be AA | CC | B. i.e 2 cuts

##### Note :

```
1) We can partition the string after the first index and before the last index.
2) Each substring after partition must be a palindrome.
3) For a string of length ‘n’, if the string is a palindrome, then a minimum 0 cuts are needed.
4) If the string contains all different characters, then ‘n-1’ cuts are needed.
5) The string consists of upper case English alphabets only with no spaces.
```

##### Input format :

```
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘T’ lines represent the ‘T’ test cases.
Each test case on a separate line contains a string ‘str’ denoting the string to be partitioned.
```

##### Output Format :

```
For each test case, return the minimum number of cuts to be done so that each partitioned substring is a palindrome.
```

##### Constraints :

```
1 <= T <= 50
1 <= length(string) <= 100
Where ‘T’ is the total number of test cases, ‘length(string)’ denotes the length of the string.
Time limit: 1 second
```