Given a string ‘str’. Find the minimum number of partitions to make in the string such that every partition of the string is a palindrome.
Given a string, make cuts in that string to make partitions containing substrings with size at least 1, and also each partition is a palindrome. For example, consider “AACCB” we can make a valid partition like A | A | CC | B. Among all such valid partitions, return the minimum number of cuts to be made such that the resulting substrings in the partitions are palindromes.
The minimum number of cuts for the above example will be AA | CC | B. i.e 2 cuts
Note :
1) We can partition the string after the first index and before the last index.
2) Each substring after partition must be a palindrome.
3) For a string of length ‘n’, if the string is a palindrome, then a minimum 0 cuts are needed.
4) If the string contains all different characters, then ‘n-1’ cuts are needed.
5) The string consists of upper case English alphabets only with no spaces.
Input format :
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘T’ lines represent the ‘T’ test cases.
Each test case on a separate line contains a string ‘str’ denoting the string to be partitioned.
Output Format :
For each test case, return the minimum number of cuts to be done so that each partitioned substring is a palindrome.
Constraints :
1 <= T <= 50
1 <= length(string) <= 100
Where ‘T’ is the total number of test cases, ‘length(string)’ denotes the length of the string.
Time limit: 1 second
CodingNinjas
author
2y
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...read more
CodingNinjas
author
2y
Dynamic Programming Approach
Following is a recursion tree for the string “ABC”
Refer Above Image
We can observe that the problem has optimal substructure and overlapping subproblems and hence can be sol...read more
CodingNinjas
author
2y
Highly Optimised Dynamic Programming Approach
In the previous approach, we calculated the minimum cut while finding all palindromic substring. If we find all palindromic substrings first and then calcu...read more
Add answer anonymously...
Top Adobe Software Quality Engineer interview questions & answers