Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

一刷

2. Manacher's Algorithm

Java: Manacher: Time Complexity - O(n)， Space Complexity - O(n)

preprocess，将输入字符串s等间距插入特殊字符'#'，目的是为了以后计算方便，不用太多考虑长度的奇偶性，不preprocess其实也可以
char[] t代表经过preprocess以后的transformed string
int[] p， p[i]是length of longest Palindromic string centerred at i，就是以i为中心，最长Palindromic string的长度
mirror代表以当前的center为中心，坐标i在center左边的镜像。因为 i - center = center - mirror，所以mirror = 2 * center - i。
下面比较重要的一点就是Manacher's Algorithm最主要的性质， 这里利用了之前计算过的最长的Palindromic String。假设之前计算过一个很长很长的Palindromic String，其中心在center， 那么我们遍历当前center的后面的元素 i 的时候，假如这个i在之前那个很长的Palindromic String的右边界范围内，那么我们就可以得到一个公式来节约重新匹配 - p[i] = Math.min(p[mirror], right - i)， 即 p[i] 的当前最小值等于 p[mirror] 和 right - i这两个值中的较小者。 这里p[mirror]是以这个mirror为中心的最长回文字符串的长度。
就比如"#a#b#a#a#b#a#"，假如当前的center在两个"a"中间的"#"，假设我们正计算以之后那个"a"为中心的结果， 因为之前的p[mirror]等于2，所以这里p[i]至少等于2和right - i中的较小者。
假如我们正计算第二个"b"为中心的结果，因为之前的p[mirror]等于4，所以p[i]至少等于4和right - i中的较小者。
有了p[mirror]和right - i这两个边界，我们就可以节约许多的重复matching
上一步确定了p[i]的最小值以后，我们就可以继续进行尝试扩展当前Palindromic。这个时候我们没有取巧的办法，只能在t中对t[i + p[i]]和t[i - p[i]]进行逐字符对比，假如他们相同，则我们增加p[i]的长度，直到求出以i为中心的最长回文串长度
在上一步找出了以i为中心的最长回文串长度后，我们比较一下当前字符串的右边界是否大于历史最长回文串右边界"right"，假如当前回文串更长，则我们更新center = i, 新的右边界right = p[i] + i。
这里我们就完成了p[i]的计算，也就是我们得到了每个以i为中心的最长回文字符串的长度。 这个时候我们再遍历一遍数组，找到其中最长的那一个，然后再对原始字符串进行substring操作就可以了

public class Solution {
    
    public String longestPalindrome(String s) {
        if(s == null || s.length == 0) return s;
        char[] t = new char[s.length()*2 + 1]; // transformed string
        int[] p = new int[t.length]; // p[i] is length of longest Palindromic string centered at i
        preprocess(s, t);
        int center = 0, right = 0;
        
        for(int i=1; i<t.length-1; i++){
            int mirror = 2*center - i; //   center - mirror = i - center,  mirror is i's mirror based on center
            if(i < right)  // if i within pre-calculated palindrome 
                p[i] = Math.min(p[mirror], right-i);
            while(i + p[i] < t.length && i - p[i] >=0 && t[i + p[i]] == t[i - p[i]]){
                p[i]++;
            }
            if(i + p[i] > right){
                center = i;
                right = i+p[i];
            }
        }
        
        center = 0;
        int maxLen = 0;
        for(int i=1; i<p.length-1; i++){
            if(p[i] > maxLen){
                center = i;
                maxLen = p[i];
            }
        }
        
        return s.substring((center - p[center] + 2)/2, (center + p[center])/2);
    }
    
    private void preprocess(String s, char[] t){
        for(int i=0; i<s.length(); i++){
            t[2*i] = '#';
            t[2*i + 1] = s.charAt(i);
        }
        t[t.length - 1] = '#';
    }
}

二刷
题解：下面的思路是选palindrome的中心点，并以中心点扩展。

public class Solution {
private int lo, maxLen;

public String longestPalindrome(String s) {
    int len = s.length();
    if (len < 2)
        return s;
    
    for (int i = 0; i < len-1; i++) {
        extendPalindrome(s, i, i);  //assume odd length, try to extend Palindrome as possible
        extendPalindrome(s, i, i+1); //assume even length.
    }
    return s.substring(lo, lo + maxLen);
}

private void extendPalindrome(String s, int j, int k) {
    while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
        j--;
        k++;
    }
    if (maxLen < k - j - 1) {
        lo = j + 1;
        maxLen = k - j - 1;
    }
}}