Palindromic Partitioning

Posted: 4 Jan, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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".
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
Approach 1

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