Algotree > Algorithms > Dynamic Programming > Minimum cuts needed to make a string palindrome

Minimum cuts needed to make a string palindrome

Finding the minimum number of cuts needed to make a given string a palindrome

Part I

The first part of the algorithm is to create a table to tell us if a given string and the substrings within it are parlindrome.
We mark a substring as palindrome in the table if
a) Characters at the beginning and end of the substring match and
b) Characters in between make a palindrome.

A two dimensional table is constructed to mark substring from position i till j as a palindrome.
For palindrome_table [ i ] [ j ] to be true, in between substring i.e substring from ( i + 1 ) and ( j - 1 ) should also be a palindrome.

This dynamic programming approach is bottom-up in nature i.e we find out the palindromes from length 1 all the way till the length of the given string.

Example:

Base Case(s):

Every single character makes a palindrome.
Same ajacent characters make a palindrome of length 2.
For substrings of size 3 upto the length of the string,
Mark substring from i till j as palindrome i.e palindrome_table [ i ] [ j ] = true, if string [ i + 1 ] [ j - 1 ] is palindrome and character at the beginning i.e [ i ] matches character at the end i.e [ j ] .

MinCuts_Palindrome

Time complexity to check if the substring is a palindrome : O ( N ² ), where N is the length of the string.

Part II

Method 1 has a time complexity of O ( n ³ ). It makes use of the table constructed earlier to check if a substring is a palindrome.
Consider the substring [ K A Y Y A ] from the original string [ K A Y Y A K ]. The minimum number of cuts needed to make [ K A Y Y A ] a palindrome is 1
i.e [ K ] & [ A Y Y A ].

So the idea is to put the cut in all the possible places. This can be done for all possible substring in a bottom up fashion.

Given String	Substring	Cut Position	Minimum Cuts
[ K A Y Y A K ]	[ K A Y Y A ] is not a palindrome.	[ K ] - [ A Y Y A ] [ K A ] - [ Y Y A ] [ K A Y ] - [ Y A ] [ K A Y Y ] - [ A ]	mincuts ( K ) + mincuts ( A Y Y A ) + 1 = 0 + 0 + 1 = 1 mincuts ( K A ) + mincuts ( Y Y A ) + 1 = 1 + 1 + 1 = 3 mincuts ( K A Y ) + mincuts ( Y A ) + 1 = 2 + 1 + 1 = 4 mincuts ( K A Y Y ) + mincuts ( A ) + 1 = 2 + 0 + 1 = 3

Program : O ( n ³ ) solution for finding the minimum cuts needed to make a string palindrome (s)

#include<iostream>
#include<string>
#include<vector>
#include<cstring>

using namespace std;

int MinimumCuts (string str) {

    const int N = str.size();

    // String of size 0 or 1 will not need any cuts to make it a palindrome
    if (N == 1 or N == 0) {
        return 0;
    }

    bool palindrome_table[N][N];
    memset(palindrome_table, false, sizeof(bool) * N * N);

    // Every single character is a palindrome.
    for (int i = 0; i < N; i++) {
        palindrome_table[i][i] = true;
    }

    // Check if 2 adjacent characters make a palindrome.
    for (int i = 0; i < N - 1; i++) {
        if (str.at(i) == str.at(i+1)) {
            palindrome_table[i][i+1] = true;
        }
    }

    // Create a table for checking if a substring [i, j] is a palindrome.
    for (int len = 3; len <= N; len++) {
        for (int beg = 0; beg < N - len + 1; beg++) {
            int end = beg + len - 1;
            if (str.at(beg) == str.at(end) and palindrome_table[beg+1][end-1] == true) {
                palindrome_table[beg][end] = true;
            }
        }
    }

    //Create a table to keep track of minimum cuts needed to make the string palindrome.
    int mincuts[N][N];
    memset (mincuts, 0, sizeof(int) * N * N);

    for(int i = 0; i < N - 1; i++) {
        if (str.at(i) == str.at(i+1)) {
            mincuts[i][i+1] = 0; // If adjacent characters are same, minimum cuts needed are 0.
        } else {
            mincuts[i][i+1] = 1; // // If adjacent characters are different, minimum cuts needed are 1
        }
    }

    // For string of length >= 3 build the mincuts table in bottom up fashion.
    for (int len = 3; len <= N; len++) {
        for (int beg = 0; beg < N - len + 1; beg++) {
            int end = beg + len - 1;

            if(palindrome_table[beg][end] == false) { // Substring [i,j] is not a palindrome.
                mincuts[beg][end] = N; // set minimum cuts to a max number 
                for (int cut = beg; cut < end; cut++) {
                    // Consider the string abcba, cuts would be ( a - bcba | ab - cba | abc - ba | abcb - a )
                    mincuts[beg][end] = min (mincuts[beg][end], mincuts[beg][cut] + mincuts[cut+1][end] + 1);
                }
            }
        }
    }

    return mincuts[0][N-1];
};

int main() {

    vector<string> strings = { "aaa", "abcbc", "kayyak", "efe", "alfaaflay", "alfaaflayalfaaflay", "abc","algootre" };

   for (const auto& str : strings) {
        cout << "Minimum cuts needed to make string [ " << str << " ] a palindrome : " << MinimumCuts (str) << endl;
   }
   return 0;
}

Output

Minimum cuts needed to make string [ aaa ] a palindrome : 0
Minimum cuts needed to make string [ abcbc ] a palindrome : 2
Minimum cuts needed to make string [ kayyak ] a palindrome : 0
Minimum cuts needed to make string [ efe ] a palindrome : 0
Minimum cuts needed to make string [ alfaaflay ] a palindrome : 1
Minimum cuts needed to make string [ alfaaflayalfaaflay ] a palindrome : 1
Minimum cuts needed to make string [ abc ] a palindrome : 2
Minimum cuts needed to make string [ algootre ] a palindrome : 6

Method II takes O ( n ² ) time to contruct the table for finding the minimum cuts. Consider the below example.
The suffix appends to all the possible prefixes to form the longest palindrome.

Given String	Substring	Prefix	Suffix	Minimum cuts needed to make a palindrome
[ K A Y Y A K ]	K	None	K	0 ( single character make a palindrome )
[ K A Y Y A K ]	K A	K	A	1 ( adjacent characters are different so 1 cut is needed for substring [ K A ] )
[ K A Y Y A K ]	K A Y	K A	Y	A Y is not a palindrome, minimum cuts needed are 1 + minimum_cuts [ K A ] = 1 + 1 = 2
[ K A Y Y A K ]	K A Y Y	K A Y	Y	Y Y is a palindrome, minimum cuts needed are 1 + minimum_cuts [ K A ] = 1 + 1 = 2
[ K A Y Y A K ]	K A Y Y A	K A Y Y	A	A Y Y A is a palindrome, minimum cuts needed are 1 + minimum_cuts [ K ] = 1 + 0 = 1
[ K A Y Y A K ]	K A Y Y A K	K A Y Y A	K	K A Y Y A K is a palindrome, minimum cuts needed = 0

Thus we get the tables as below


Substring	K	K A	K A Y	K A Y Y	K A Y Y A	K A Y Y A K
Index	0	1	2	3	4	5
Minimum Cuts	0 Base case	1 Base case	2	2	1	0

Program : O ( n ² ) solution for finding the minimum cuts needed to make a string palindrome (s)

#include<iostream>
#include<string>
#include<vector>
#include<cstring>

using namespace std;

int MinimumCuts (string str) {

    const int N = str.size();

    // String of size 0 or 1 will not need any cuts to make it a palindrome
    if (N == 1 or N == 0) {
        return 0;
    }

    bool palindrome_table[N][N];
    memset(palindrome_table, false, sizeof(bool) * N * N);

    // Every single character is a palindrome.
    for(int i=0; i<N; i++) {
        palindrome_table[i][i] = true;
    }

    // Check if 2 adjacent characters make a palindrome.
    for(int i=0; i<N-1; i++) {
        if (str.at(i) == str.at(i+1)) {
            palindrome_table[i][i+1] = true;
        }
    }

    // Create a table for checking if a substring [i, j] is a palindrome.
    for(int len=3; len <= N; len++) {
        for(int i=0; i < N-len+1; i++) {
            int j = i + len - 1;
            if (str.at(i) == str.at(j) and palindrome_table[i+1][j-1] == true) {
                palindrome_table[i][j] = true;
            }
        }
    }

    //Create a minimum cuts suffix table to keep track of the cuts needed to make a string palindrome.
    int mincuts[N];
    memset (mincuts, 0, sizeof(int) * N);

    mincuts[0] = 0;

    if (str.at(0) == str.at(1)) {
        mincuts[1] = 0;
    } else {
        mincuts[1] = 1;
    }

    for (int current = 2; current < N; current++) {
        // set minimum cuts to previously found cuts + 1 (presume that it needs 1 more cut).
        mincuts[current] = mincuts[current-1] + 1;
        for (int prev = current-1; prev >= 0; prev --) {
            // Check if the substring [prev, current] is a palindrome
            if (palindrome_table[prev][current] == true) {
                if (prev > 0) {
                    mincuts[current] = min (mincuts[current], 1 + mincuts[prev-1]);
                } else if (prev == 0) {
                    mincuts[current] = 0; // the substring [0, current] is a palindrome.
                }
            }
        }
    }
    return mincuts[N-1];
};

int main() {

    vector<string> strings = { "aaa", "abcbc", "kayyak", "efe", "alfaaflay", "alfaaflayalfaaflay", "abc","algootre", "fiefhgdcdcgfeibggchibffahiededbbegegdfibdbfdadfbdbceaadeceeefiheibahgececggaehbdcgebaigfacifhdbecbebfhiefchaaheiichgdbheacfbhfiaffaecicbegdgeiaiccghggdfggbebdaefcagihbdhhigdgbghbahhhdagbdaefeccfiaifffcfehfcdiiieibadcedibbedgfegibefagfccahfcbegdfdhhdgfhgbchiaieehdgdabhidhfeecgfiibediiafacagigbhchcdhbaigdcedggehhgdhedaebchcafcdehcffdiagcafcgiidhdhedgaaegdchibhdaegdfdaiiidcihifbfidechicighbcbgibadbabieaafgeagfhebfaheaeeibagdfhadifafghbfihehgcgggffgbfccgafigieadfehieafaehaggeeaaaehggffccddchibegfhdfafhadgeieggiigacbfgcagigbhbhefcadafhafdiegahbhccidbeeagcgebehheebfaechceefdiafgeddhdfcadfdafbhiifigcbddahbabbeedidhaieagheihhgffbfbiacgdaifbedaegbhigghfeiahcdieghhdabdggfcgbafgibiifdeefcbegcfcdihaeacihgdchihdadifeifdgecbchgdgdcifedacfddhhbcagaicbebbiadgbddcbagbafeadhddaeebdgdebafabghcabdhdgieiahggddigefddccfccibifgbfcdccghgceigdfdbghdihechfabhbacifgbiiiihcgifhdbhfcaiefhccibebcahidachfabicbdabibiachahggffiibbgchbidfbbhfcicfafgcagaaadbacddfiigdiiffhbbehaaacidggfbhgeaghigihggfcdcidbfccahhgaffiibbhidhdacacdfebedbiacaidaachegffaiiegeabfdgdcgdacfcfhdcbfiaaifgfaciacfghagceaaebhhibbieehhcbiggabefbeigcbhbcidbfhfcgdddgdffghidbbbfbdhcgabaagddcebaechbbiegeiggbabdhgghciheabdibefdfghbfbfebidhicdhbeghebeddgfdfhefebiiebdchifbcbahaddhbfafbbcebiigadhgcfbebgbebhfddgdeehhgdegaeedfadegfeihcgeefbbagbbacbgggciehdhiggcgaaicceeaefgcehfhfdciaghcbbgdihbhecfbgffefhgiefgeiggcebgaacefidghdfdhiabgibchdicdehahbibeddegfciaeaffgbefbbeihbafbagagedgbdadfdggfeaebaidchgdbcifhahgfdcehbahhdggcdggceiabhhafghegfdiegbcadgaecdcdddfhicabdfhbdiiceiegiedecdifhbhhfhgdbhibbdgafhgdcheefdhifgddchadbdggiidhbhegbdfdidhhfbehibiaacdfbiagcbheabaaebfeaeafbgigiefeaeheabifgcfibiddadicheahgbfhbhddaheghddceedigddhchecaghdegigbegcbfgbggdgbbigegffhcfcbbebdchffhddbfhhfgegggibhafiebcfgeaeehgdgbccbfghagfdbdfcbcigbigaccecfehcffahiafgabfcaefbghccieehhhiighcfeabffggfchfdgcfhadgidabdceediefdccceidcfbfiiaidechhbhdccccaigeegcaicabbifigcghcefaafaefd" };

   for (const auto& str : strings) {
        cout << "Minimum cuts needed to make string [ " << str << " ] a palindrome : " << MinimumCuts (str) << endl;
   }
   return 0;
}

Output

Minimum cuts needed to make string [ aaa ] a palindrome : 0
Minimum cuts needed to make string [ abcbc ] a palindrome : 2
Minimum cuts needed to make string [ kayyak ] a palindrome : 0
Minimum cuts needed to make string [ efe ] a palindrome : 0
Minimum cuts needed to make string [ alfaaflay ] a palindrome : 1
Minimum cuts needed to make string [ alfaaflayalfaaflay ] a palindrome : 1
Minimum cuts needed to make string [ abc ] a palindrome : 2
Minimum cuts needed to make string [ algootre ] a palindrome : 6
Minimum cuts needed to make string [ fiefhgdcdcgfeibggchibffahiededbbegegdfibdbfdadfbdbceaadeceeefiheibahgececggaehbdcgebaigfacifhdbecbebfhiefchaaheiichgdbheacfbhfiaffaecicbegdgeiaiccghggdfggbebdaefcagihbdhhigdgbghbahhhdagbdaefeccfiaifffcfehfcdiiieibadcedibbedgfegibefagfccahfcbegdfdhhdgfhgbchiaieehdgdabhidhfeecgfiibediiafacagigbhchcdhbaigdcedggehhgdhedaebchcafcdehcffdiagcafcgiidhdhedgaaegdchibhdaegdfdaiiidcihifbfidechicighbcbgibadbabieaafgeagfhebfaheaeeibagdfhadifafghbfihehgcgggffgbfccgafigieadfehieafaehaggeeaaaehggffccddchibegfhdfafhadgeieggiigacbfgcagigbhbhefcadafhafdiegahbhccidbeeagcgebehheebfaechceefdiafgeddhdfcadfdafbhiifigcbddahbabbeedidhaieagheihhgffbfbiacgdaifbedaegbhigghfeiahcdieghhdabdggfcgbafgibiifdeefcbegcfcdihaeacihgdchihdadifeifdgecbchgdgdcifedacfddhhbcagaicbebbiadgbddcbagbafeadhddaeebdgdebafabghcabdhdgieiahggddigefddccfccibifgbfcdccghgceigdfdbghdihechfabhbacifgbiiiihcgifhdbhfcaiefhccibebcahidachfabicbdabibiachahggffiibbgchbidfbbhfcicfafgcagaaadbacddfiigdiiffhbbehaaacidggfbhgeaghigihggfcdcidbfccahhgaffiibbhidhdacacdfebedbiacaidaachegffaiiegeabfdgdcgdacfcfhdcbfiaaifgfaciacfghagceaaebhhibbieehhcbiggabefbeigcbhbcidbfhfcgdddgdffghidbbbfbdhcgabaagddcebaechbbiegeiggbabdhgghciheabdibefdfghbfbfebidhicdhbeghebeddgfdfhefebiiebdchifbcbahaddhbfafbbcebiigadhgcfbebgbebhfddgdeehhgdegaeedfadegfeihcgeefbbagbbacbgggciehdhiggcgaaicceeaefgcehfhfdciaghcbbgdihbhecfbgffefhgiefgeiggcebgaacefidghdfdhiabgibchdicdehahbibeddegfciaeaffgbefbbeihbafbagagedgbdadfdggfeaebaidchgdbcifhahgfdcehbahhdggcdggceiabhhafghegfdiegbcadgaecdcdddfhicabdfhbdiiceiegiedecdifhbhhfhgdbhibbdgafhgdcheefdhifgddchadbdggiidhbhegbdfdidhhfbehibiaacdfbiagcbheabaaebfeaeafbgigiefeaeheabifgcfibiddadicheahgbfhbhddaheghddceedigddhchecaghdegigbegcbfgbggdgbbigegffhcfcbbebdchffhddbfhhfgegggibhafiebcfgeaeehgdgbccbfghagfdbdfcbcigbigaccecfehcffahiafgabfcaefbghccieehhhiighcfeabffggfchfdgcfhadgidabdceediefdccceidcfbfiiaidechhbhdccccaigeegcaicabbifigcghcefaafaefd ] a palindrome : 1345