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 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".
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'.
For each test case, print an integer denoting the minimum number of partitions required such that each partition is a palindrome.
You don’t have to print anything, it has already been taken care of. Just complete the function.
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
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 :
- 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.
- 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’.