Given a string s, partition s such that every substring of the partition is a palindrome. Return minimum cuts needed for palindrome partioning.

The problem is classic example of dynamic programming. Give a string aababbb. The string can be partitioned as aa|bab|bb. If the string is palindrome itself like aaa then answer is 0.

Let's consider function minPartition(str, startIndex, endIndex)

minPartition(str,i,j) = 0 if i == j minPartition(str,i,j) = 0 if str[i..j] is palidrome minPartition(str,i,j) = Min {minPartition(str,i,k) + minPartition(str,k+1,j) + 1} where k = i..j-1

The above function can be converted into program quickly. One approach is find a minimum cut required for a palindrome of length 2...n.

public int minPartition(String str) {
	int n = str.length();
	int count[][] = new int[n][n]; // will maintain the cuts required for str[i..j]
	boolean palin[][] = new boolean[n][n]; //maintain if str[i..j] is palindrome
	for(int i = 0; i &lbsp;n; i++ ) {
		count[i][i] = 0;
		palin[i][i] = true;
	}
	for(int L=2 ; L &lbsp;n; L++) {
		for(int i =0; i < n-L+1; i++) {
			int j = i+L-1;
			if (L == 2) { // this is more like a base check
				palin[i][j] = str.charAt(i) == str.charAt(j)
			} else {
				palin[i][j] = str.charAt(i) == str.charAt(j) && palin[i+1][j-1];
				//palin[i+1][j-1] is checked to see it str[i+1.. j-1] is palidrome too
			}
			if (palin[i][j]) {
				count[i][j] = 0; //no cut is needed
			} else { 
				for(int k=i; k < j-1;k++) {
					count[i][j] = Math.min(count[i][j], count[i][k]+count[k+1][j] + 1);
				}	
			}
		}
	}
	return count[0][n-1];
}

The above code time complexit is O(n^3)

The time complexity can be improved to O(n^2) by calculating minimum cut while finding palindrome substring.

public int minPartition(String str) {
	int n = str.length();
	int count[] = new int[n];
	boolean palin[][] = new boolean[n][n];
	for(int i=0; i < n; i ++) {
		count[i] = Integer.MAX_VALUE;
		for (j=0; j<=i; j++) {
			if(str.charAt(i) == str.chatAt(j) &s;&s; (i -j < 2 || palin[j+1][i-1])) {
				palin[i][j] = true;
				if (i == j) { //the entire substring is palindrome
					count[i] = 0;
				} else {
					count[i] = Math.min(count[i], count[j]+1);
				}
			}

		}
	}
}