Palindrome Partitioning ll

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
9 upvotes
Asked in companies
MicrosoftAmazonDavis Software

Problem statement

Ninja contains a string 'STR'. He has to partition the string 'STR' into a minimum number of partitions such that each partition is a palindrome.

Ninja is stuck and needs your help. Your task is to print the minimum number of cuts required such that each partition of the string 'STR' is a palindrome.

For example:

For the string “abc”, we can create 2 partitions and get 3 palindromic strings "a", "b" and "c". 

For the string “abbcb”, we can create 2 partitions and get 3 palindrome strings "a", "b" and "bcb".
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first and only line of each test case contains the string 'STR'.
Output Format: 
For each test case, print an integer denoting the minimum number of partitions required such that each partition is a palindrome.
Note 
You don’t have to print anything, it has already been taken care of. Just complete the function.
Constraints: 
1 <= T <= 10
1 <=  | STR | <= 200
STR contains lowercase English alphabets only.

Where ‘T’ is the total number of test cases and | STR | represents the length of the string STR. 

Time Limit: 1 sec
Sample Input 1:
2 
rohit 
abb
Sample Output 1:
4
1
Explanation For Sample Input 1:
In the first test case, the minimum partitions required are 4 which will make palindrome substrings as: ‘r’, ‘o’, ‘h’, ‘i’ and ‘t’.

In the second test case, the minimum partitions required is 1 which will make palindrome substrings as: ‘a’ and ‘bb’.
Sample Input 2:
2
abba
aakaashh
Sample Output 2:
0
2
Explanation For Sample Input 2:
In the first test case, the given string itself is a palindrome. Thus, there is no need to make any cuts. 

In the second test case, thepartitioned strings are as follows: ‘aakaa’, ‘s’ and ‘hh’.
Hint

Can you do this recursively? Try to solve the problem by solving its subproblems first.

Approaches (4)
Recursion

This problem can be solved by solving its subproblems and then combining the solutions of the solved subproblems to solve the original problem. We will do this using recursion. The idea is to use recursion to reduce the big problem into several small subproblems.

 

Here is the algorithm :

 

  1. We will call a recursive function ‘minimumCutsHelper’ that takes the string, the starting index, and the ending index of the string. This function will generate all possible partitions and will decide the minimum possible cuts required.
  2. The algorithm for the helper function will be as follows and ‘START’ is the starting index, ‘END’ is the ending index and ‘STR’ is the given string.
    int minimumCutsHelper(STR, start, end):
    • If ‘START’ = ‘END’, the string contains only 1 character which will definitely be a palindrome. Thus, return 0.
    • If ‘STR[ START to END ]’ is a palindrome, no partition is needed, return 0.
    • Create an ‘ANSWER’ variable to store the final answer.
    • Now, we calculate ‘ANSWER’ for every possible partition,
    • For ‘k’ in the range start to ‘END’ - 1:
      • Call minimumCutsHelper(STR, start, k) + 1 + minimumCutsHelper(STR, k + 1, end) and store it in a variable say ‘CURRENTCUTS’.
      • Update answer by ‘CURRENTCUTS’ if ‘CURRENTCUTS’ is less than the answer.
    • Return ‘ANSWER’.
Time Complexity

O(N * (2 ^ N)), where N is the length of the string ‘STR’.

 

The length of the string is N and the partition can be made between any two letters. Thus, there are 2 ^ (N - 1) positions. Hence, there will be 2 ^ (N - 1) recursive calls and in each call, we are checking whether the substring is a palindrome or not in O(N) time. Thus, the final time complexity is O(N * 2 ^ (N)). 

Space Complexity

O(N), where N is the length of the string ‘STR’.

 

We are not using any external data structure. Only recursion stack space of O(N) size is used by the algorithm.

Code Solution
(100% EXP penalty)
Palindrome Partitioning ll
Full screen
Console