Description: Given a string S, we have divide it in minimum cuts, so that each part is a palindrome. We have to find this minimum no. of cuts.If the String S is a palindrome itself, the no. of cuts needed is 0.

Example:

“a b a b c b a”

In the above example, minimum number of cuts needed is 2 and string is cut into “aba”,”bcb” and “a”.

Algorithm and implementation:

We’ll solve this problem using dynamic programming.
We define:
A[i][j]={1, if the substring between indexes ‘i’ and ‘j’ is a palindrome
0, otherwise }
B[i][j]= Minimum no of cuts needed for palindrome partitioning of substring between ‘i’ and ‘j’
B[i][j]={
0, if the substring between ‘i’ and ‘j’ is a palindrome(A[i][j]=1)
min value of B[i][k] +B[k+1][j]+1 where   i<=k<=j, otherwise
}
Minimum no of cuts need is B[0][n-1].

/*The following function Returns the minimum number of cuts needed to partition a string such that every part is a palindrome*/

int minimum_Palindrome_Partion(char *str)
{
int n = strlen(str);
/*n stores length of the string. */
int B[n][n];
int A[n][n];
int i=0, j, k;
int  Len;
i=0;
while(i<n)
{
B[i][i] = 0;
A[i][i] = 1;/*every substring of length 1 is a palindrome. So zero cuts needed.*/
i++;
}

for(Len=2; Len<=n; L++)
{
/*Consider substring of length Len*/
/*’i’ is starting index*/
for(i=0; i<n-Len+1; i++)
{
j = i+Len-1; /*Ending index*/
/* If Len is 2, then we just need to compare two characters. Else need to check two corner characters and value of A[i+1][j-1]*/
if(Len== 2)
A[i][j] = (str[i] == str[j]);
else
A[i][j] = (str[i] == str[j]) && A[i+1][j-1];
if(A[i][j] == 1)/*if str[i..j] is a palindrome*/
B[i][j] = 0;
else
{
/*Get minimum cost cut from every possible location from i->j?*/
B[i][j] = INT_MAX;
for(k=i; k<=j-1; k++)
B[i][j] = min (B[i][j], B[i][k] + B[k+1][j]+1);
}
}
}
return B[0][n-1]; /*minimum no of cuts needed*/
}
Time Complexity:

O(n^3) where n is the length of the string.

Go to top