public int minCut(String s) {
    	if (s.isEmpty())
    		return 0;
    	if (isPalindrome(s, 0, s.length() - 1))
    	    return 0;
    	
    	int cuts[] = new int[s.length()];
    	
    	for (int i = 1; i < s.length(); i++)
    	{
    		cuts[i] = s.length();
    		for (int j = 0; j <= i; j++)
    		{
    			if (isPalindrome(s, j, i))
    			{
    				if (j == 0)
    					cuts[i] = 0;
    				else
    					cuts[i] = Math.min(cuts[i], cuts[j-1] + 1);
    			}
    		}
    	}
    	
    	return cuts[s.length() - 1];
    }