Palindrome Partitioning ll

Hard
0/120
Average time to solve is 40m
profile
Contributed by
89 upvotes
Asked in companies
AmazonAdobePayPal

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
aaccb


Sample Output 1 :
2


Explanation of sample input 1 :
We can make a valid partition like aa | cc | b.


Sample Input 2 :
ababa


Sample Output 2 :
0


Explanation of sample input 2 :
The string is already a palindrome, so we need not make any partition.


Sample Input 3:
aababa


Sample Output 3:
1


Expected time complexity :
You can submit a solution of time complexity O(n ^ 3) but also try to write the solution having complexity O(n ^ 2).


Constraints :
1 <= 'n' <= 100

Time limit: 1 second
Hint

Find all possible ways to partition the string.

Approaches (3)
Brute Force Approach
  • 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.
Time Complexity

O(n * 2 ^ n), ‘n’ is the length of the string.

In the worst case, all possible combinations for length ‘n’ are recursively found, and in each case, we check if it is a palindrome that takes order of ‘n’ time.

Space Complexity

O(n), ‘n’ is the length of the string.

Recursive stack uses space of the order ‘n’.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Palindrome Partitioning ll
Full screen
Console