 New update is available. Click here to update.
Last Updated: 11 Nov, 2020
##### Palindrome Partitioning ll
Hard
Problem statement #### Find the minimum number of partitions in the string so that no partition is empty and every partitioned substring is a palindrome.

##### Example :
``````Input: 'str' = "aaccb"

Output: 2

Explanation: We can make a valid partition like aa | cc | b.
``````
##### Input format :
``````The first line contains the string 'str', the string to be partitioned.
``````

##### Output Format :
``````Print the minimum number of cuts to be done so that each partitioned substring is a palindrome.
``````

##### Note :
``````You do not need to print anything; it has already been taken care of. Just implement the given function.
`````` Approaches

## 01Approach • 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. 