Update appNew update is available. Click here to update.
Last Updated: 11 Nov, 2020
Palindrome Partitioning ll
Hard
Problem statement

You are given a string 'str' of length 'n'.


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.