Cacher is the code snippet organizer for pro developers

public class Solution {
    // Transfer S into T
    // For example, S = "abba", T = "^#a#b#b#a#$".
	// ^ and $ signs are sentinels appended to each end to avoid bounds checking
	public static String preProcess(String s) {
		int n = s.length();
		if (n == 0)
			return "^$";
		String ret = "^";
		for (int i = 0; i < n; i++) {
			ret += "#" + s.charAt(i);
		}
		ret += "#$";
		return ret;
	}
	//this is the O(N) solution
	public static String longestPalindrome(String s) {
		if (s.length() == 1)
			return s;
		else {
			String T = preProcess(s);
			int n = T.length();
			int[] p = new int[n];
			int C = 0, R = 0; // C stands for Center, R stands for the rightmost element
			for (int i = 1; i < n - 1; i++) {
				int i_mirror = 2 * C - i; // equals to i' = C - (i-C); symmetric element
				p[i] = (R > i) ? Math.min(R - i, p[i_mirror]) : 0;
				// Attempt to expand palindrome centered at i
				while (T.charAt(i + 1 + p[i]) == T.charAt(i - 1 - p[i]))
					p[i]++;
				// If palindrome centered at i expand past R,
				// adjust center based on expanded palindrome.
				if (i + p[i] > R) {
					C = i;
					R = i + p[i];
				}
			}
			// Find the maximum element in P
			int maxLen = 0;
			int centerIndex = 0;
			for (int i = 1; i < n - 1; i++) {
				if (p[i] > maxLen) {
					maxLen = p[i];
					centerIndex = i;
				}
			}
			return s.substring((centerIndex - 1 - maxLen) / 2, (centerIndex + maxLen) / 2);			
		}
	}
}

/**
 * Given a string S, find the longest palindromic substring in S. 
 * You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
 */

public class Solution {
    public String longestPalindrome(String s) {
        int length = s.length();
        String res = s.substring(0, 1);
        for(int i = 0; i < length; i++) {
            // base case (i, i) and (i, i + 1);
            String ps = getPalindrome(s, i, i);
            res = (ps.length() > res.length()) ? ps : res;
            ps = getPalindrome(s, i, i + 1);
            res = (ps.length() > res.length()) ? ps : res;
        }
        return res;
    }
    // expand aroung center
    private String getPalindrome(String s, int l, int r){
        while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
            l--;
            r++;
        }
        return s.substring(l + 1, r);   
    }
}