Palindrome Partitioning ll
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
- 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 each recursive function call, we divide the string into 2 subsequences of all possible sizes.
- Let ‘i’, ‘j’ be the starting and ending indices of a substring respectively.
- If ‘i’ is equal to ‘j’ or str[ ‘i’.....’j’ ] is a palindrome, we return 0.
- Otherwise, we start a loop with variable ‘k’ from starting index of string ‘i’ and ending index of string ‘j’-1 and then recursively call the function for the substring with starting index ‘i’ and ending index ‘j’ to find the minimum cuts in each subsequence.
- Do this for all possible positions where we can cut the string and take the minimum over all of them.
- In the end, the recursive function would return the minimum number of partitions needed for the complete string.
Following is a recursion tree for the string “ABC”
We can observe that the problem has optimal substructure and overlapping subproblems and hence can be solved using dynamic programming. The idea is to store the results of subproblems so that we do not have to re-compute them when they are needed.
Below is an approach, in which smaller subproblems are stored first which are used to solve the larger sub-problems. The below approach computes two 2-Dimensional arrays 'isPalindrome[][]' and 'cuts[][]' where 'isPalindrome[i][j]' stores if a substring with starting index ‘i’ and ending index ‘j’ is a palindrome or not.(isPalindrome[i][i] is true as every string of length 1 is a palindrome)
cuts[i][j] stores the minimum number of cuts needed for a substring with starting index ‘i’ and ending index ‘j’
- Run a loop where 2<=L<=N. Consider ‘L’ as the length of the substring.
- For each substring of length ‘L’ set different possible starting indices ‘i’ where ‘i’ ranges from 0 to L-1 and calculate 'cuts[i][j]' where ‘j=i+L-1’ i.e the last index of the string with starting index ‘i’ and length ‘L’ and 'cuts[i][j]' is the minimum cuts needed for the string ‘str[ i…..j]’.
We can optimise it for the following cases:
- If ‘L’ is equal to 2, we just need to compare 2 characters. Else we need to check two corner characters and value of ‘isPalindrome[i+1][j-1]’
- If ‘str[ i….j]’ is palindrome then ‘cuts[i][j]=0’
- Otherwise, we take a variable ‘k’ where ‘i’<=k<=’j’ and make a cut at every kth location to find the number of cuts. We repeat this at every possible location starting from ‘i’ to ‘j’ and get a minimum cost cut. And store it at cuts[ i ][ j ].
- Lastly, return ‘cuts[0][n-1]’ stores the minimum number of cuts needed.
In the previous approach, we calculated the minimum cut while finding all palindromic substring. If we find all palindromic substrings first and then calculate the minimum cut, the solution would optimize.
We can do that in the following way:
- Compute one 2 Dimensional arrays 'isPalindrome[][]' and an array 'cuts[]' where 'isPalindrome[i][j]' stores if a substring with starting index ‘i’ and ending index ‘j’ is a palindrome or not.
- Mark isPalindrome[i][i] true as every substring of length 1 is a palindrome.cuts[i] is the minimum number of cuts needed for a palindrome partitioning of substring str[0..i]. Now, find all the palindromic substrings in the given string for each length ‘L’ and for every starting index ‘i’. In the following way:
- If the value of ‘L’ is 2 we just compare the 2 characters.
- Otherwise, we check the first and last character of the substring and also if isPalindrome[i+1][j-1] is true. If yes, we mark the current substring as a palindrome.
Now that we know all the substrings which are Palindromes, We can efficiently find the minimum cuts in the following way:
- Let cuts[i] is the minimum number of cuts needed for a palindrome partitioning of substring str[0..i]
- If isPalindrome[0][i] is true we say cuts[i]=0.
- Otherwise, we first initialize the value of cuts[i] to be infinite.
- Then for each ‘i’ we take a variable’ j’ and initialize it to 0.
- Then we loop through j such that 0 <= j < i and find update cuts[i], if 1+cuts[j] is less than the current value of cuts[i] i.e we find a better way of partitioning the substring str[0...i] with lesser number of cuts.
- We add an extra 1 because the substring is not palindrome we need to make a cut.
- Otherwise cuts[i] = cuts[j] + 1 for all j < i and if str[j + 1...i] is a palindrome
- Finally, our answer lies at cuts[n-1] which is the final answer
