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.


“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’
              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;
B[i][i] = 0;        
A[i][i] = 1;/*every substring of length 1 is a palindrome. So zero cuts needed.*/
    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]);
                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;
                /*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