Abbas and Hatim were two friends who lived in Yemen. They are learning Datastructures and Algorithms in their school. One day the teacher asked them a difficult problem. The problem is known as palindromic partitioning. Given a string, we need to divide the string into different substrings such that each of the substrings is a palindrome. We need to do it such that the number of partitions is minimum. Abbas and Hatim had no clue to solve this problem. Let us help them tackle this problem.
Given a string S of length N, we need to partition it, so each substring is a palindrome. The number of partitions should be minimum. Return the minimum number of partitions.
For example,
S = ”acabbadeeff”
Here the minimum number of partitions is 5. The palindrome substrings are {“a”, ”c”, “abba”, “d”, “ee”, “ff”}.
S = “aabbaa”
Here the number of partitions is 0. The string itself is a palindrome, so we don’t need to partition it.
S = “abcd”
Here the number of partitions is 3. All the characters of the string are different. Therefore the number of partitions is equal to string length -1.
Approach 1
It's a brute-force strategy. To solve it, we employ recursion. We can divide the problem into subproblems that partition the string into the smallest number of cuts possible. We divide the string into two subsequences of all possible sizes with each recursive function call. The starting and ending indices of a substring are ‘i’ and 'j,' respectively. We return 0 if ‘i’ equals 'j' or if str['i'.....'j'] is a palindrome.
Otherwise, we start a loop with variable 'k' from starting index of string ‘i’ to ending index of string 'j'-1, and then run the function for the substring with starting index ‘i’ and ending index 'j' to discover the minimum cuts in each subsequence recursively. Carry out this procedure for all possible spots where the string can be cut, and take the smallest of them all. The recursive function would finally yield the smallest number of partitions required for the entire string. Let's take a look at how the aforementioned strategy is implemented.
Implementation
#include<bits/stdc++.h> usingnamespacestd;
boolisPalindrome(string str, int i, int j) { while (i <= j) { if (str[i++] != str[j--]) { returnfalse; } } returntrue; }
intminPalinPartition(string str, int i, int j) {
if (i == j || isPalindrome(str, i, j)) { return0; }
int min = INT_MAX;
for (int k = i; k <= j - 1; k++) { int count = 1 + minPalinPartition(str, i, k) + minPalinPartition(str, k + 1, j); if (count < min) { min = count; } }
return min; }
intpalindromePartitioning(string str) { int n = str.size(); return minPalinPartition(str, 0, n - 1); }
intmain(){ cout<<"Enter the number of test cases"<<endl; int t; cin>>t; cout<<"Enter the strings"<<endl; while(t--){ string str; cin>>str; cout<<palindromePartitioning(str)<<endl; } return0; }
The time complexity of the above algorithm is O(N*power(2, N)). Here N is the length of the substring. In the worst case, we find all possible combinations for N, and to check whether it is palindrome or not, it checks O(N) time.
Space Complexity
The space complexity of the above algorithm is O(N). The recursive stack uses O(N) space.
Approach 2
This is a method in which smaller subproblems are saved first, and then the bigger subproblems are solved. The following method generates two 2-Dimensional arrays, 'isPalindrome[][]' and 'cuts[][]', where 'isPalindrome[i][j]' saves whether or not a substring with starting index I and ending index 'j' is a palindrome. (Every string of length 1 is a palindrome. Hence isPalindrome[i][i] is true.) The minimum number of cuts required for a substring with starting index ‘i’ and ending index 'j' is stored in cuts[i][j].
Run a loop from 2 to N. Consider 'L' to be the substring's length. Set several alternatives starting indices ‘i’ for each substring of length ‘L', where ‘i’ varies from 0 to L-1, then calculate 'cuts[i][j]' where ‘j=i+L-1'. 'cuts[i][j]' is the minimal cuts required for the string'str[i.....j]', i.e., the final index of the string with starting index I and length 'L', and 'cuts[i][j]' is the last index of the string with starting index I and length 'L'.
We can make it better in the following scenarios:
We only need to compare two characters if ‘L' equals 2. Otherwise, two corner characters and the value of 'isPalindrome[i+1][j-1]' must be checked.
‘cuts[i][j]=0' if ‘str[ i....j]' is a palindrome.
Otherwise, we use the variable ‘k', where ‘i'=k='j', and cut at every kth place to get the number of cuts. We do this at every conceivable place, starting with I and ending with 'j,' to attain the smallest cost reduction. And put it away in cuts[i][j]. Finally, the variable 'cuts[0][n-1]' is used to store the minimal number of cuts required.
Implementation
#include<bits/stdc++.h> usingnamespacestd;
intpalindromePartitioning(string str) {
int n = str.length(); int cuts[n][n]; bool isPalindrome[n][n];
for (int i = 0; i < n; i++) { isPalindrome[i][i] = true; cuts[i][i] = 0; }
for (int L = 2; L <= n; L++) {
for (int i = 0; i < n - L + 1; i++) { int j = i + L - 1;
cuts[i][j] = INT_MAX; for (int k = i; k <= j - 1; k++) { cuts[i][j] = min(cuts[i][j], cuts[i][k] + cuts[k + 1][j] + 1); } } } }
return cuts[0][n - 1]; }
intmain(){ cout<<"Enter the number of test cases"<<endl; int t; cin>>t; cout<<"Enter the strings"<<endl; while(t--){ string str; cin>>str; cout<<palindromePartitioning(str)<<endl; } return0; }
Input
Enter the number of test cases
3
acabbadeeff
aabbaa
abcd
Output
5
0
3
Time Complexity
The time complexity is O(N^3), ‘n’ is the length of the string. We have an order of N^2 loop for each length ‘N’.
Space Complexity
The space complexity is O(N^2), ‘N’ is the length of the string. A 2 Dimensional array of size ‘N*N’ is used.
We estimated the smallest cut while searching for all palindromic substrings in the prior method. The solution will optimize if we first discover all palindromic substrings and then calculate the minimum cut. This can be accomplished in the following manner:
Compute 'isPalindrome[i][j]' and an array 'cuts[]' are two-dimensional arrays that hold whether a substring with starting index ‘i’ and ending index 'j' is a palindrome or not. isPalindrome[i][i] Mark is a palindrome. Because any substring of length 1 is a palindrome, this is true. The minimal number of cuts required for a palindrome partitioning of substring str[0..i] is cuts[i]. Now, for each length 'L' and starting index, ’i’ locate all the palindromic substrings in the supplied string. To put it another way: We just compare the two letters if the value of 'L' equals 2. Otherwise, we check the substring's initial and end characters, as well as whether isPalindrome[i+1][j-1] is true. If yes, we mark the current substring as a palindrome.
Now that we know all of the substrings that are Palindromes, we can get the minimal cuts quickly by doing the following:
Let cuts[i] be the minimal number of cuts required to divide substring str[0] into palindromes .i] We state cuts[i]=0 if isPalindrome[0][i] is true. Otherwise, we'll set the value of cuts[i] to infinity first. Then, for each ‘i’, we create a variable called ‘j' and set it to 0.
Then, if 1+cuts[j] is smaller than the current value of cuts[i], we identify a better technique of partitioning the substring str[0...i] with fewer cuts. We added another because the substring isn't palindrome and we need to trim it. Otherwise, for all j I cuts[i] = cuts[j] + 1 and if str[j + i] is a palindrome, cuts[i] = cuts[j] + 1. Finally, our solution is cuts[n-1], which is the final solution.
Implementation
#include<bits/stdc++.h> usingnamespacestd;
intpalindromePartitioning(string str) { int n = str.size(); int cuts[n]; bool isPalindrome[n][n];
int i, j, k, L; for (i = 0; i < n; i++) { isPalindrome[i][i] = true; }
for (L = 2; L <= n; L++) { for (i = 0; i < n - L + 1; i++) { j = i + L - 1;
for (i = 0; i < n; i++) { if (isPalindrome[0][i] == true) { cuts[i] = 0; } else { cuts[i] = INT_MAX; for (j = 0; j < i; j++) { if (isPalindrome[j + 1][i] == true && 1 + cuts[j] < cuts[i]) cuts[i] = 1 + cuts[j]; } } } return cuts[n - 1]; }
intmain(){ cout<<"Enter the number of test cases"<<endl; int t; cin>>t; cout<<"Enter the strings"<<endl; while(t--){ string str; cin>>str; cout<<palindromePartitioning(str)<<endl; } return0; }
Input
Enter the number of test cases
3
acabbadeeff
aabbaa
abcd
Output
5
0
3
Time Complexity
The time complexity of the above algorithm is O(N*N). As finding all palindromic substrings takes an order of power(N,2) and finding minimum cuts takes an order of power(N,2), the final complexity is an order of power(N,2).
Space Complexity
The space complexity is O(power(N,2)), ‘N’ is the length of the string. We are using a 2 Dimensional array of size ‘n*n.’
In this blog, we learned how to solve the Palindromic Partitioning problem. It is a difficult level problem. We solved it using three different approaches. We improved from O(N*power(2, N)) to O(N*N) using dynamic programming. To learn Dynamic programming, try solving problems such as Longest Palindromic Subsequence & take our Data structures and Algorithms course at Coding Ninjas.
38+ registered 