1.题目描述

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.//aba也是有效的答案

Example:
Input: "cbbd"
Output: "bb"

给定一个字符串s，找到当中的最长回文子串。你可能需要假设s的最大长度是1000。

这里解释一下回文串的定义：
“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。

题目中的回文子串就是满足回文串性质的最长子串。

2.解题思路

看到这道题的时候，第一个想法就是暴力解法，扫描以每个字符串为中心的回文串，在其中找到最长的那个回文子串，就可以的出结果，这中思路没有什么技巧，比较好想，代码也比较好写，但是边界问题还有一些细节需要注意：

当字符串为空或者只有一个的情况。
遇到第一个字符和最后一个字符的时候怎么处理。
aba和abba情况的区分。
这是最简单也是最笨的解决这种问题的思路，在discuss里面有更好的解决办法，能把复杂度降到O(n)的神奇算法，我根据算法实现了代码，但是超时了，好无奈。这里给出一个博客，总结了这道题的各种解法：
博客地址，还有一篇专门介绍这种方法的博客

3.代码

class Solution { 
 
public  String test(String s,int l,int r) { 
		int n = s.length(); 
		while(l>=0 && r<=n-1 && s.charAt(l)==s.charAt(r)) { 
		//限定l和r的范围，并比较是否相等，相等就对范围进行扩张。 
			l--; 
			r++; 
		} 
		return s.substring(l+1, r); 
		//这里就要仔细 考虑边界情况以及当自己和自己比较的时候 
		//l--，但是可能存在下个不满足条件，而substring函数是不包括r这个边界的 
	} 
	public  String longestPalindrome(String s) { 
		int slen = s.length(); 
	   if(slen==0) 
		   return null;//若字符串为空 
	   //int[] p = new int[slen]; 
	   String longString = "";//新建一个空的字符串 
	   for(int i=0;i<slen;i++) { 
		String p1= test(s,i,i+1);//这种情况是对于abba这种中间有重复的情况，是偶数 
	    String p2 = test(s,i,i);//这种情况对应于aba这种情况，是奇数 
	    if(p1.length()>p2.length()) {//获得当前的最大回文串 
	    	longString = longString.length()>p1.length()? longString:p1; 
	    } 
	    else 
	    	longString = longString.length()>p2.length()? longString:p2; 
	   } 
	   return longString; 
	} 
	 
} 

下面是leetcode上排名前几的代码，它的基本思路也是查找以每个字符为中心的回文串，但是它优化了碰到重复字符时的情况：

class Solution { 
    private int max_length; 
    private int start; 
 
    public String longestPalindrome(String s) { 
        if(s.length() < 2) 
            return s; 
        for(int i = 0; i < s.length();) { 
            i = extendPalindrome2sides(s, i); 
        } 
        return s.substring(start, start + max_length); 
    } 
 
    private int extendPalindrome2sides(String s, int anchor) { 
        //Skip duplicate characters. 
        int j = anchor, k = anchor; 
        while(k < s.length() - 1 && s.charAt(k) == s.charAt(k + 1)) k++; 
		//这句代码跳过了重复字符，也就是处理了偶数的那种情况 
		//当是奇数的时候，不会进入循环 
        int next_i = k + 1;//计算出下一个需要进行回文计算的字符 
         
        while(j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) { 
            j--; 
            k++; 
        } 
        int cur_leng = (--k) - (++j) + 1; 
		//这个--k和++j,理解起来有点模糊，但是写的很优雅 
		//还是想到边界情况：当最后一个不满足的时候，但是index已经定位到它们， 
		//这就需要把左边还原 
        if(cur_leng > max_length) { 
            start = j; 
            max_length = cur_leng; 
        } 
         
        return next_i; 
    } 
} 

传说中的马拉车算法：

	public static String longestPalindrome1(String s) { 
		if(s.length()==0) 
			return null; 
		String tmp = "$#"; 
		for(int i= 0;i<s.length();i++) { 
			tmp+=s.charAt(i); 
			tmp+="#"; 
		} 
		tmp+="^"; 
		int [] p=new int[tmp.length()]; 
		 
		int c = 0,r=0,len=0,cen=0; 
		for(int i=1;i<tmp.length()-1;i++) { 
			p[i] = r>i? Math.min(p[2*c-i],r-i):1; 
			while(tmp.charAt(i-p[i])==tmp.charAt(i+p[i])) 
				p[i]++; 
			if(r<i+p[i]) { 
				r=i+p[i]; 
				c=i; 
			} 
			if(p[i]>len) { 
				len=p[i]; 
				cen = i; 
			} 
		} 
		int pos  =(cen-len)/2; 
		return s.substring(pos, pos+len-1); 
		 
	} 