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