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);
}
}
}
}
}