// Given an input word, find the longest palindrome in the word.

public class LongestPalindromeInAString {
	private static boolean isPalindrome(String string) {
		int start = 0;
		int end = string.length() - 1;

		while (start < end) {
			if (string.charAt(start) != string.charAt(end)) {
				return false;
			}

			start++;
			end--;
		}

		return true;
	}

	private static String longestPalindrome(String string) {
		if (string == null) {
			return null;
		}

		int max = 1;
		int start = 0;
		int length = string.length();

		for (int i = 1; i < length; i++) {
			// Even length palindrome.
			int low = i - 1;
			int high = i;
			while (low >= 0 && high < length && string.charAt(low) == string.charAt(high)) {
				if (max < high - low + 1) {
					start = low;
					max = high - low + 1;
				}

				low--;
				high++;
			}

			// Odd length palindrome.
			low = i - 1;
			high = i + 1;
			while (low >= 0 && high < length && string.charAt(low) == string.charAt(high)) {
				if (max < high - low + 1) {
					start = low;
					max = high - low + 1;
				}

				low--;
				high++;
			}
		}

		return string.substring(start, start + max);
	}

	public static void main(String[] args) {
		System.out.println("isPalindrome: madam: " + isPalindrome("madam"));
		System.out.println("isPalindrome: racecar: " + isPalindrome("racecar"));
		System.out.println("isPalindrome: racecars: " + isPalindrome("racecars"));

		System.out.println("longestPalindrome: madam: " + longestPalindrome("madam"));
		System.out.println("longestPalindrome: racecars: " + longestPalindrome("racecars"));
		System.out.println("longestPalindrome: abccba: " + longestPalindrome("abccba"));
	}
}
