Palindrome Min Cut

Algorithm/Insights

1. Initialize a palindrome DP table of size nxn where n is the length of the given String
2. Set single length palindrome values to 1
3. Loop from lengths 2 to n and check palindrome for each length using the following rule
    palindrome[i][j] = palindrome[i+1][j-1] + 2, if s[i] == s[j]
    palindrome[i][j] = Math.max(palindrome[i+1][j], palindrome[i][j-1]), if s[i] != s[j]
4. after the loop, return palindrome[0][n-1]

Code Snippet

			
package com.ideserve.virendra.questions;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * <br><br>
 * Palindrome Min Cut - Dynamic Programming Solution</b><br>
 * Given a string S, find the minimum number of cuts required to separate the string into a set of palindromes
 * <br><br>
 * Example: <br>
 * Input String: <br>
 * "banana"
 * <br>
 * Output: <br>
 * 1
 * <br><br>
 * <a href="https://www.youtube.com/watch?v=U4yPae3GEO0">Longest Palindromic Subsequence Solution Youtube Link</a> 
 * @author Virendra
 *
 */
 
 public class PalindromePartitionMinCut {
	
	public static int partition(String s) {
		  int n = s.length();
		  boolean palindrome[][] = new boolean[n][n]; //boolean table
		  
		  //Trivial case: single letter palindromes
		  for (int i = 0; i < n; i++) {
			  palindrome[i][i] = true;
		  }
		  
		  //Finding palindromes of two characters.
		  for (int i = 0; i < n-1; i++) {
		    if (s.charAt(i) == s.charAt(i+1)) {
		      palindrome[i][i+1] = true;
		    }
		  }
		  
		  //Finding palindromes of length 3 to n
		  for (int curr_len = 3; curr_len <= n; curr_len++) {
		    for (int i = 0; i < n-curr_len+1; i++) {
		      int j = i+curr_len-1;
		      if (s.charAt(i) == s.charAt(j) //1. The first and last characters should match 
		    	  && palindrome[i+1][j-1]) //2. Rest of the substring should be a palindrome
		      {
		    	palindrome[i][j] = true; 
		      }
		    }
		  }
		  
		  int[] cuts = new int[n];
		  for(int i=0; i<n; i++)
		  {
			  int temp = Integer.MAX_VALUE;
			  if(palindrome[0][i])
				  cuts[i] = 0;
			  else
			  {
				  for(int j=0; j<i; j++)
				  {
					 if((palindrome[j+1][i]) && temp > cuts[j] + 1) 
					 {
						 temp = cuts[j] + 1;
					 }
				  }
				  cuts[i] = temp;
			  }			  
		  }
		  return cuts[n-1];
		}

	public static void main(String args[])
	{
		System.out.println(partition("bananna"));
	}
}
		

Order of the Algorithm

Time Complexity is O(n^2)
Space Complexity is O(n^2)