Solution Approach
Approach 1: Brute force
Let’s try to solve it using a bruteforce 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 substrings 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. Since it is a palindrome, we don’t need to partition it. Thus, it doesn’t contribute to the count.
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 substring 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.
C++ Implementation
#include <iostream>
#include <climits>
using namespace std;
bool isPalindrome(string str, int i, int j)
{
while (i < j)
{
if (str[i++] != str[j])
{
return false;
}
}
return true;
}
int minPalinPartition(string &str, int i, int j)
{
if (i == j  isPalindrome(str, i, j))
{
return 0;
}
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;
}
int palindromePartitioning(string &str)
{
int n = str.length();
return minPalinPartition(str, 0, n  1);
}
int main()
{
string str;
cout << "Enter the string: ";
cin >> str;
cout << "Required minimum number of cuts are: " << palindromePartitioning(str);
return 0;
}
Input
Enter the string: acabbadeeff
Output
Required minimum number of cuts are: 5
Time Complexity
O(N *(2 ^ N)), where ‘N’ is the length of the string.
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
O(N), here ‘N’ is the length of the string.
Because the recursive stack uses O(N) space in the worst case.
Approach 2: Bottomup DP
This is a method in which smaller subproblems are saved first, and then the bigger subproblems are solved. The following method generates two 2dimensional arrays, 'IS_PALINDROME[ ][ ]' and 'CUTS[ ][ ]', where 'IS_PALINDROME[i][j]' saves whether or not a substring with starting index ‘i’ and ending index 'j' is a palindrome.
Note: Every string of length 1 is a palindrome. Hence, IS_PALINDROME[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. . .]', i.e., the final index of the string with starting index ‘i’ and length 'L'.

'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 'IS_PALINDROME[i + 1][j  1]' must be checked.

‘CUTS[i][j] = 0' if ‘STR[. . .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.
C++ Implementation
#include<iostream>
#include<string>
using namespace std;
int palindromePartitioning(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;
// For two length substrings.
if (L == 2) {
isPalindrome[i][j] = (str[i] == str[j]);
}
/* Updating isPalindrome table based on characters at i and j of str and previous value of isPalindrome[i][j]*/
else {
isPalindrome[i][j] = (str[i] == str[j]) && isPalindrome[i + 1][j  1];
}
// cuts[i][j] = 0 as isPalindrome[i][j] is true.
if (isPalindrome[i][j] == true) {
cuts[i][j] = 0;
}
/* Updating cuts[i][j] table as isPalindrome[i][j] is false */
else {
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];
}
int main(){
string str;
cin>>str;
// Function Call.
int ans= palindromePartitioning(str);
cout<<ans<<endl;
return 0;
}
Input
acabbadeeff
Output
5
Time Complexity
O(N^{3}), where ‘N’ is the length of the string.
We have an order of N ^ 2 loops for each length ‘N’. We update the cuts table in a nested loop. Iterating over the cuts array takes O(N). So overall it takes O(N3).
Space Complexity
O(N^2), where ‘N’ is the length of the string.
A 2dimensional array of size ‘N ^ 2’ is used.
Approach 3: Efficient Approach
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]' is a twodimensional array that holds whether a substring with starting index ‘I’ and ending index 'J' is a palindrome or not. 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][J1] 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. 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’ CUTS[I] = CUTS[J] + 1 and if str[J + i] is a palindrome, CUTS[I] = CUTS[J] + 1. Finally, our solution is CUTS[N1], which is the final solution.
C++ Implementation
#include<iostream>
#include<string>
using namespace std;
int palindromePartitioning(string str) {
int n = str.size();
int cuts[n];
bool isPalindrome[n][n];
int i, j, k, L;
/* A single charater is a palindrome*/
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 two length strings */
if (L == 2) {
isPalindrome[i][j] = (str[i] == str[j]);
}
/* Updating isPalindrome table based on string values and previous value of isPalindrome */
else {
isPalindrome[i][j] = (str[i] == str[j]) && isPalindrome[i + 1][j  1];
}
}
}
for (i = 0; i < n; i++) {
/* cuts[i][j] = 0 as isPalindrome[i][j] is true */
if (isPalindrome[0][i] == true) {
cuts[i] = 0;
}
else {
/* Updating cuts table */
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];
}
int main(){
string str;
cin>>str;
// Function Call.
int ans= palindromePartitioning(str);
cout<<ans<<endl;
return 0;
}
Input
acabbadeeff
Output
5
Time Complexity
O(N^2), where ‘N’ is the length of the string.
As finding all palindromic substrings takes an order of O(N^2) and finding minimum cuts takes an order of O(N^2), the final complexity is an order of O(N^2).
Space Complexity
The space complexity is O(N^2), where ‘N’ is the length of the string.
We are using a 2dimensional array of size ‘N^2’.
Also check out  Substr C++
Frequently Asked Questions
What is the vector in C++?
Vector is a dynamically sized array in the C++ STL library. It is very useful as it provides various builtin functions to add, insert, remove, pop elements, etc.
How can we add an element at the end of a vector?
To add an element at the end of a vector, we can use vector_name.push_back() function. This function takes the element to be added as an argument.
How is the performance of an algorithm measured?
To measure the performance of an algorithm and compare two algorithms, we use the time and space complexities of the algorithm.
What is meant by the brute force approach?
Brute force is the most basic approach to solving a problem which takes the most time.
What is a palindrome?
A palindrome is a string or sequence of characters that reads the same forwards and backward.
Conclusion
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*(2^N)) to O(N^2) using dynamic programming.
Check out this problem  Check If A String Is Palindrome
Head to the Guided Path on the Coding Ninjas Studio and upskill in Data Structures and Algorithms, Competitive Programming, System Design, and many more courses.
If you want to Practice top Coding Problems, attempt mock tests, or read interview experiences, head to the Coding Ninjas Studio, our practice platform.
Recommended Readings:
We wish you Good Luck!🎈 Please upvote our blog 🏆 and help other ninjas grow.