# Palindromic Partitioning

Posted: 4 Jan, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### 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.