Make delicious recipes!

Find minimum no of cuts to get all palindromes from a string



Problem: Given a string, find the minimum no of cuts to get all palindromes from a string.

Example: If string = "abbacdc", then we can get "abba","cdc" in just one cut.
If string = "abcd", then 3 cuts are required to get "a","b","c" and "d" (because any single char is also a palindrome)


Solution:
import java.util.ArrayList;
import java.util.List;

public class MinimumCutsForAllPalindromes
{
    public static void main(String[] args)
    {
        minCutsForAllPalindromes("a");
        minCutsForAllPalindromes("ab");
        minCutsForAllPalindromes("aba");
        minCutsForAllPalindromes("abcb");
        minCutsForAllPalindromes("abbaab");
        minCutsForAllPalindromes("ababba");
        minCutsForAllPalindromes("ababcbbabcbababa");
    }

    /**
     * Main function to find minimum number of cuts to get all palindromes in a string
     */
    static int minCutsForAllPalindromes(String str)
    {
        boolean[][] isPalindrome = findPalindromes(str);

        int N = str.length();
        
        // List at each index stores the start-indices of palindromes that lie
        // between that index and the end
        ArrayList<ArrayList<Integer>> palindromsFromKthToEnd =
                             new ArrayList<ArrayList<Integer>>(N);
        for (int i=0; i<N; i++)
            palindromsFromKthToEnd.add(new ArrayList<Integer>());

        // Last char is a single char string.
        // So its a palindrome of length 1
        palindromsFromKthToEnd.get(N-1).add(N-1);

        // Find palindromes in all the other paths
        for(int i = N-2; i >= 0; i--)
        {
            if(isPalindrome[i][N-1])
            {
                // Whole string is a palindrome from i till end,
                // So number of cuts required here is minimum = 0
                palindromsFromKthToEnd.get(i).clear();
                palindromsFromKthToEnd.get(i).add(i);
            }
            else
            {
                for(int k = N-2; k >= i; k--)
                {
                    if(isPalindrome[i][k])
                    {
                        int newPalindromsCount = 1 + palindromsFromKthToEnd.get(k+1).size(); 

                        if (palindromsFromKthToEnd.get(i).isEmpty() ||
                            newPalindromsCount < palindromsFromKthToEnd.get(i).size())
                        {
                            ArrayList<Integer> pK = palindromsFromKthToEnd.get(i);
                            pK.clear();
                            pK.add(0, i);
                            pK.addAll(palindromsFromKthToEnd.get(k+1));
                        }
                    }
                }
            }
        }

        printPalindromes(str, palindromsFromKthToEnd);

        // No of cuts required is 1 less than then number of palindromes.
        return (palindromsFromKthToEnd.get(0).size() - 1);
    }

    /**
     * Returns a boolean lookup such that every cell - isPalindrome[i][j] is
     * true only if the string from i to j index is a palindrome.
     * 
     *  Points to be noted:
     * Observe how we run two loops and each loop goes from a smaller size string to a
     * larger size string. This is very important aspect of this function. The loops
     * should always handle a smaller substring first before they can handle a larger one.
     * That is why:
     *    outer loop variable 'i' goes from end to start and
     *    inner loop variable 'j' goes from 'i' to end (It cannot go from end to 'i')
     */
    private static boolean[][] findPalindromes(String str)
    {
        int N = str.length();
        boolean isPalindrome[][] = new boolean[N][N];

        for (int i = N-1; i >= 0; i--)
        {
            for (int j = i; j < N; j++)
            {
                if (i== j)
                {
                    isPalindrome[i][j] = true;
                }
                else if(str.charAt(i) != str.charAt(j))
                {
                    isPalindrome[i][j] = false;
                }
                else
                {
                    isPalindrome[i][j] = ((j-i == 1)?true:isPalindrome[i+1][j-1]);
                }
            }
        }
        return isPalindrome;
    }

    /**
     * Utility function to print all the palindromes
     */
    static void printPalindromes(String str,
            ArrayList<ArrayList<Integer>> palindromsTillEnd)
    {
        System.out.println("\n\nMinimum number of palindromes in " + str +
                            ":\n-------------------------------------------");
        List<Integer> indices = palindromsTillEnd.get(0);
        int i;
        for (i=0; i<indices.size()-1; i++)
        {
            int begin = indices.get(i);
            int end = indices.get(i+1);
            System.out.println(str.substring(begin, end));
        }
        int begin = indices.get(i);
        System.out.println(str.substring(begin));
    }
}
Sample Execution


Minimum number of palindromes in a:
-------------------------------------------
a


Minimum number of palindromes in ab:
-------------------------------------------
a
b


Minimum number of palindromes in aba:
-------------------------------------------
aba


Minimum number of palindromes in abcb:
-------------------------------------------
a
bcb


Minimum number of palindromes in abbaab:
-------------------------------------------
abba
a
b


Minimum number of palindromes in ababba:
-------------------------------------------
aba
bb
a


Minimum number of palindromes in ababcbbabcbababa:
-------------------------------------------
aba
bcb
babcbab
aba

Order of execution: O(n2)





Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal