给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: “babad”

输出: “bab”

注意: “aba” 也是一个有效答案。

示例 2：

输入: “cbbd”

输出: “bb”

这个题目第一感觉，肯定是暴力破解，双重循环，但效率肯定低下，稍微好一点的方法就是中心扩散， 比如 abcdfabcdfg, 字符f左右扩散， 就可以得到abcdfabcd。

java 实现代码如下：

public String longestPalindrome(String s) {
 //中心发散法
 int length = s.length();
 if (length == 0)
 return "";
 int longSize = 1;
 String longStr = s.substring(0, 1);
 for (int i = 0; i < s.length(); i++) {
 String odd = centerSpread(s, length, i, i);
 String even = centerSpread(s, length, i, i + 1);
 String maxLen = odd.length() > even.length() ? odd : even;
 if (maxLen.length() > longSize) {
 longSize = maxLen.length();
 longStr = maxLen;
 }
 }
 return longStr;
}
static String centerSpread(String s, int len, int left, int  right ) {
 int leftIndex = left;
 int rightIndex = right;
 while (leftIndex >= 0 && rightIndex < len && s.charAt(leftIndex) == s.charAt(rightIndex)) {
 leftIndex--;
 rightIndex++;
 }
 return s.substring(leftIndex + 1, rightIndex);
}
 

时间复杂度 也为O(n*n), 其实还有更好的解决办法， Manacher 算法 ，有兴趣的可以查看下