/**
 * 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.
 *
 * Tags: String
 */
class LongestPalindromicSubstring {

    public static void main(String[] args) {

    }
    
    /**
     * Manacher's Algorithm, O(n) Time.
     * S = “abba” => T = “#a#b#b#a#”.
     */
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) return "";

        int length = s.length();
        int max = 0;
        String result = "";
        
        for (int i = 1; i <= 2 * length - 1; i++) {
            int count = 1;
            while (i - count >= 0 && i + count <= 2 * length  && get(s, i - count) == get(s, i + count)) count++;
            count--; // there will be one extra count for the outbound #
            if (count > max) {
                result = s.substring((i - count) / 2, (i + count) / 2);
                max = count;
            }
        }

        return result;
    }

    private char get(String s, int i) {
        if (i % 2 == 0) return '#';
        else return s.charAt(i / 2);
    }

    /**
     * Manacher's Algorithm, O(n) Time.
     * S = “abba” => T = “^#a#b#b#a#$”.
     * http://www.felix021.com/blog/read.php?2040
     * http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
     */
    public String longestPalindrome(String s) {
        String t = preProcess(s);
        int n = t.length();
        int[] p = new int[n];
        int range = 0, center = 0;

        for (int i = 1; i < n - 1; i++) {
            int mirror = 2 * center - i; // mirror of i to center
            p[i] = range > i ? Math.min(range - i, p[mirror]) : 0;
            while (t.charAt(i + 1 + p[i]) == t.charAt(i - 1 - p[i])) p[i]++;
            if (i + p[i] > range) {
                center = i;
                range = i + p[i];
            }
        }

        int maxLen = 0;
        int centerIdx = 0;
        for (int i = 1; i < n - 1; i++) {
            if (p[i] > maxLen) {
                maxLen = p[i];
                centerIdx = i;
            }
        }
        return s.substring((centerIdx - 1 - maxLen) / 2, (centerIdx - 1 + maxLen) / 2);
    }

    private String preProcess(String s) {
        int n = s.length();
        if (n == 0) return "^$";
        String res = "^";
        for (int i = 0; i < n; i++) {
            res += "#" + s.substring(i, i + 1);
        }
        res += "#$";
        return res;
    }

    /**
     * O(n^2) Time, O(1) Space
     * Expand from center character and center of two chars
     * Update result according to the returned length
     */
    public String longestPalindromeB(String s) {
        if (s == null || s.length() == 0) return "";
        String longest = s.substring(0, 1);
        int len = s.length();
        for (int i = 0; i < len - 1; i++) {
            String s1 = expandAroundCenter(s, i, i);
            if (s1.length() > longest.length()) longest = s1;
            String s2 = expandAroundCenter(s, i, i + 1);
            if (s2.length() > longest.length()) longest = s2;
        }
        return longest;
    }

    /**
     * Search for range in both direction
     */
    private String expandAroundCenter(String s, int i, int j) {
        int l = i;
        int r = j;
        int n = s.length();
        while (l >= 0 && r <= n - 1 && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        return s.substring(l + 1, r); // note the range is from l + 1 to r - 1
    }
}
@@ -286,16 +286,169 @@
 args) %7B%0A
+        LongestPalindromicSubstring l = new LongestPalindromicSubstring();%0A        String s = %22abba%22;%0A        System.out.println(l.longestPalindrome(s));
 %0A    %7D%0A 
@@ -662,19 +662,16 @@
  int len
-gth
  = s.len
@@ -693,24 +693,38 @@
 int max = 0;
+ // max length
 %0A        Str
@@ -730,19 +730,16 @@
 ring res
-ult
  = %22%22;%0A 
@@ -782,19 +782,16 @@
  2 * len
-gth
  - 1; i+
@@ -786,32 +786,47 @@
  len - 1; i++) %7B
+ // skip two #s
 %0A            int
@@ -894,20 +894,16 @@
  2 * len
-gth 
  && get(
@@ -1050,16 +1050,62 @@
 %3E max) %7B
+ // update max and result when longer is found
 %0A       
@@ -1116,19 +1116,16 @@
      res
-ult
  = s.sub
@@ -1242,19 +1242,185 @@
  res
-ult;
+;%0A    %7D%0A    %0A    /**%0A     * Insert char to the original input string%0A     * If the index is even, return #%0A     * If the index is odd, return char in the original string
 %0A    
-%7D%0A
+ */
 %0A   
@@ -1787,32 +1787,33 @@
 ongestPalindrome
+B
 (String s) %7B%0A   
@@ -3080,33 +3080,33 @@
 ongestPalindrome
-B
+C
 (String s) %7B%0A   
@@ -3935,8 +3935,9 @@
 %0A    %7D%0A%7D
+%0A

Updated longest palindromic substring