Palindrome partitioning

Introduction

Let us discuss a famous problem 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. It is a class of problems that can be solved optimally using dynamic programming. Let us understand the problem statement and all the possible approaches to solving the problem.

Problem Statement

Given a string ‘S’ of length ‘N’, we need to partition it, so that each substring is a palindrome. The number of partitions should be minimum. Return the minimum number of partitions.

Given string, S = “acdabbadeeff”

Here the minimum number of partitions required is 6. The palindrome substrings are {“a”, ”c”, ”d”, “abba”, “d”, “ee”, “ff”}.

These are the cuts that make each substring a palindrome.

Example

S = ”aabbaa” is a palindrome, so we don’t need to partition it. Here the minimum number of partitions required is 0.
S = “abcd” Here the minimum number of partitions required is 3. All the characters of the string are different. Therefore the number of partitions is equal to string length -1. Now, since you have understood the problem statement, please attempt it once on our Coding platform Coding Ninjas Studio.

Solution Approach

Approach 1: Brute force

Let’s try to solve it using 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 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;
}

You can also try this code with Online C++ Compiler

Run Code

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: Bottom-up DP

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, '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;
}

You can also try this code with Online C++ Compiler

Run Code

Input

acabbadeeff

Output

Time Complexity

O(N³), 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 2-dimensional 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 two-dimensional 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][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. 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[N-1], 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;
}

You can also try this code with Online C++ Compiler

Run Code

Input

acabbadeeff

Output

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 2-dimensional 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 built-in 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.

Introduction

Problem Statement

Solution Approach

Approach 1: Brute force

C++ Implementation

Input

Output

Time Complexity

Space Complexity

Approach 2: Bottom-up DP

C++ Implementation

Input

Output

Time Complexity

Space Complexity

Approach 3: Efficient Approach

C++ Implementation

Input

Output

Time Complexity

Space Complexity

Frequently Asked Questions

What is the vector in C++?

How can we add an element at the end of a vector?

How is the performance of an algorithm measured?

What is meant by the brute force approach?

What is a palindrome?

Conclusion