Provides a solution to the "Minimum Cuts for Palindrome Partitioning" problem http://basicalgos.blogspot.com/2013/03/67-palindrome-partitioning.html

Partitioner.java

/**
 * Provides methods to determine minimum the number of cuts
 * required to split a string into palindromes.
 *
 * @author Scott Rossillo
 */
public final class Partitioner {

	/**
	 * Returns true if the given string is a palindrome.
	 */
	public static boolean isPalindrome(final String s) {

		int i = 0;
		int j = s.length() - 1;

		while (i < j) {
			if (s.charAt(i++) != s.charAt(j--)) {
				return false;
			}
		}

		return true;
	}

	/**
	 * Returns the minimum number of cuts required to partition
	 * the given string for palindrome partitioning.
	 */
	public static int minCuts(final String s) {

		int cuts = -1;

		for (int i = 0; i < s.length(); i++) {
			for (int j = s.length(); j > 0; j--) {
				final String t = s.substring(i, j);
				if (isPalindrome(t)) {
					cuts++;
					i = j - 1;
					break;
				}
			}
		}

		return cuts;
	}
}

PartitionerTests.java

import org.junit.Assert;
import org.junit.Test;

/**
 * Provides palindrome partitioner unit tests.
 *
 * @author Scott Rossillo
 */
public final class PartitionerTests {

	@Test
	public void testIsPalindrome() {
		Assert.assertTrue(Partitioner.isPalindrome("madam"));
		Assert.assertTrue(Partitioner.isPalindrome("a"));
		Assert.assertTrue(Partitioner.isPalindrome("aa"));
		Assert.assertTrue(Partitioner.isPalindrome("aba"));
		Assert.assertTrue(Partitioner.isPalindrome("abba"));
		Assert.assertTrue(Partitioner.isPalindrome("abccba"));
		Assert.assertTrue(Partitioner.isPalindrome("abcddcba"));
	}

	@Test
	public void testIsPalindromeNot() {
		Assert.assertFalse(Partitioner.isPalindrome("madams"));
		Assert.assertFalse(Partitioner.isPalindrome("smadam"));
		Assert.assertFalse(Partitioner.isPalindrome("ab"));
		Assert.assertFalse(Partitioner.isPalindrome("abc"));
		Assert.assertFalse(Partitioner.isPalindrome("abcd"));
	}

	@Test
	public void testMinCutsZero() {
		Assert.assertEquals(0, Partitioner.minCuts("madam"));
		Assert.assertEquals(0, Partitioner.minCuts("a"));
		Assert.assertEquals(0, Partitioner.minCuts("aa"));
	}

	@Test
	public void testMinCutsOne() {
		Assert.assertEquals(1, Partitioner.minCuts("aab"));
		Assert.assertEquals(1, Partitioner.minCuts("baa"));
		Assert.assertEquals(2, Partitioner.minCuts("aaba"));
		Assert.assertEquals(2, Partitioner.minCuts("abzz"));
		Assert.assertEquals(1, Partitioner.minCuts("madams"));
		Assert.assertEquals(1, Partitioner.minCuts("smadam"));
	}

	@Test
	public void testMinCutsTwo() {
		Assert.assertEquals(2, Partitioner.minCuts("abc"));
		Assert.assertEquals(2, Partitioner.minCuts("aabc"));
		Assert.assertEquals(2, Partitioner.minCuts("abcc"));
		Assert.assertEquals(2, Partitioner.minCuts("XXXXmomZ"));
		Assert.assertEquals(2, Partitioner.minCuts("XmaamZ"));
	}

	@Test
	public void testMinCutsThree() {
		Assert.assertEquals(3, Partitioner.minCuts("XXXXmomZqq"));
		Assert.assertEquals(3, Partitioner.minCuts("XmaamZqq"));
	}
}