Palindrome Partitioning Problem using Dynamic Programming

Expand DP problem in detail: Note for maintainers

Given a string, a partitioning is known as palindrome partitioning if all partitions of the string are palindromes. Find the minimum number of cuts required to make such partitions.

The Dynamic Programming approach takes O(N^3) time and makes use of two array structures.

Example of Palindrome Partitioning

For example, the string "abaabbbab" requires a minimum of 3 cuts to ensure partitions, "aba|abba|b" that are palindromic. If the string itself is a palindrome, the minimum number of cuts will be 0. If all the characters of a string of length 'n' are distinct, the minimum number of cuts will be 'n-1'.
If our string is a palindrome, we return 0 else we recursively create cuts at all possible places and compute the minimum cost amongst them.

The naive recursive approach will have an exponential time complexity as we check for all possible permutations that helps us obtain palindrome partitionings.
Application of dynamic programming to solve the above problem would result in reduction of time complexity to a large extent because we make use of additional space to store the intermediate results of our computation.

Dynamic Programming makes use of the top down apporach, i.e. it computes from the values of smaller subproblems and combines them to calculate the overall result.
This is where dynamic programming differs from the naive rescursive solution and the top-down approach reduces the time complexity to a large extent as well.

Why Dynamic Programming for Palindrome Partitioning?

In context to the above partitioning problem, let us take an example string = "abbabbaa".By trial and error we know the minimum number of cuts required is 3.
Now let us view this problem from the context of a compiler. The compiler is going to call the recursive function until it hits the base case of presence of 1 character as a substring. The recursion tree one can draw to compute the result, we can observe the subproblems repeating themselves. To avoid the computation of results for the same subproblem again and again, we need to store the results of such a computation by making use of extra space. This is how one observes making use of dynamic programming for the above problem is essential.

Optimal Substructure Property of Palindrome Partitioning

Dynamic programming has the optimal substructure property associated with it, which means we can define a property that helps us break our function and provide a definition to it. The optimal substructure is generally derived from the recursion tree or the recurrence relation of the problem. For the palindromic partitioning problem, the optimal substructure is as follows:

i = starting index (0)
j = ending index (n-1)

minimumPartition(str,i,j) = 0 ; if i == j (string of length 1)
minimumPartition(str,i,j) = 0 ; if str is palindrome

minimumPartition(str,i,j) = minimumPartition(str,i,k)+1
                            + minimumPartition(str,k+1,j)
                            // where k varies from i+1 to j

the last relation we see is pretty conceivable, once we ascertain that a substring is palindromic, we increment our count by one which depicts that atleast one cut has been made and proceed in the left and right directions.

Dynamic Programming for Palindrome Partitioning

We maintain two array for DP:

• C[i][j] = Minimum number of cuts needed for palindrome partitioning of substring of str()
• P[i][j] = true if substring of str() is a palindrome, else false

C[i][j] is 0 if P[i][j] as no cuts are required to make a Palindrome a Palindrome

Base Cases:

Number of characters=1

C[i][i]=0 and P[i][i]=true 

as single character is always a palindrome

Number of characters=2

P[i][j] = (str[i] == str[j])

Number of characters>2

P[i][j] = (str[i] == str[j]) && P[i + 1][j - 1];

Calculating C[i][j]

• If substring (i,j) is a Palindrome that is P[i][j] == true, set C[i][j] = 0

• If substring (i,j) is not a Palindrome: Consider dividing the string (i,j) into (i,k)+(k,j) and compute C[i][j] accordingly

C[i][j] = INT_MAX; 
for (k = i; k <= j - 1; k++) 
    C[i][j] = min(C[i][j], C[i][k] + C[k + 1][j] + 1); 

Our answer is C[0][N-1] that is covering the entire string.

Implementation

#include <bits/stdc++.h> 
using namespace std; 

// returns the minimum number of cuts needed to partition a string 
// such that every part is a palindrome 
int minPalPartion(string str) 
{ 
	// Get the length of the string 
	int n = str.size(); 

	/* Create two 2d arrays to build the solution in bottom up manner 
	C[i][j] = Minimum number of cuts needed for palindrome partitioning 
				of substring of str() 
	P[i][j] = true if substring of str() is a palindrome, else false 
	Note that C[i][j] is 0 if P[i][j] is true */
	int C[n][n]; 
	bool P[n][n]; 

	int i, j, k, m; 
    
    // base case:
	// every substring of length 1 is a palindrome 
	for (i = 0; i < n; i++) 
	{ 
		P[i][i] = true; 
        // true because substring str(i,i) is only one character
		C[i][i] = 0; 
        // string of length 1 is a palindrome
	} 
    // we further build our solution from the values filled in diagnols
	/* m is the length of substring. Build the 
	solution in bottom up manner by 
	considering all substrings of 
	length from 2 to n */
	
	for (m = 2; m <= n; m++) 
	{ 
		// For substring of length m, set 
		// different possible starting indexes 
		for (i = 0; i < n - m + 1; i++) 
		{ 
			j = i + m - 1; // Set ending index 

			// If m is 2 (j = i-1), then we just need to 
			// compare two characters. Else 
			// need to check two corner characters 
			// and value of P[i+1][j-1] 
			if (m == 2) 
				P[i][j] = (str[i] == str[j]);  //palindrome, set true
			else
				P[i][j] = (str[i] == str[j]) && P[i + 1][j - 1]; 
                //usage of boolean operator AND for fast computation
                
			// if str(i,j) is palindrome, then C[i][j] is 0 
			if (P[i][j] == true) 
				C[i][j] = 0; 
			else
			{ 
				// make a cut at every possible 
				// location starting from i to j, 
				// and get the minimum cost cut. 
				C[i][j] = INT_MAX; 
				for (k = i; k <= j - 1; k++) 
					C[i][j] = min(C[i][j], C[i][k] + C[k + 1][j] + 1); 
                    // applying the optimal substructure property
			} 
		} 
	} 

	// Return the min cut value for 
	// complete string, str(0,n-1) 
	return C[0][n - 1]; // final result is present here
} 

// Driver code 
int main() 
{ 
	char str[] = "abbabbababa"; // try making use of other examples as well
	cout<<"Min cuts needed for Palindrome Partitioning is "<<minimumPartion(str); 
	return 0; 
} 

Complexity analysis:

Time Complexity = O(n^3) // three loops in iteration
Space Complexity = O(n^2) // two auxiliary 2d arrays

Question:

Draw the recursion tree for the input string = "ababbabbaaabba" and calculate the number of cuts required to form the palindromic partitions.