Palindrome Partitioning ll

Posted: 11 Nov, 2020
Difficulty: Hard


Try Problem

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
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.
Try Problem