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.