# Palindrome Partitioning ll

Posted: 11 Nov, 2020
Difficulty: Moderate

## PROBLEM STATEMENT

#### 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
`````` Approach 1
• This is a recursive approach.
• We can break the problem into a set of related subproblems which partition the given string in such a way that yields the lowest possible total cuts.
• In each recursive function call, we divide the string into 2 subsequences of all possible sizes.
• Let ‘i’, ‘j’ be the starting and ending indices of a substring respectively.
• If ‘i’ is equal to ‘j’ or str[ ‘i’.....’j’ ] is a palindrome, we return 0.
• Otherwise, we start a loop with variable ‘k’ from starting index of string ‘i’ and ending index of string ‘j’-1 and then recursively call the function for the substring with starting index ‘i’ and   ending index ‘j’  to find the minimum cuts in each subsequence.
• Do this for all possible positions where we can cut the string and take the minimum over all of them.
• In the end, the recursive function would return the minimum number of partitions needed for the complete string.