Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

## 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> palindromsFromKthToEnd = new ArrayList>(N); for (int i=0; i()); // 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 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> palindromsTillEnd) { System.out.println("\n\nMinimum number of palindromes in " + str + ":\n-------------------------------------------"); List indices = palindromsTillEnd.get(0); int i; for (i=0; i

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: