给你一个字符串 s，找到 s 中最长的 回文 子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

解题思路

中心扩散法，找到一个“中心”，然后向两边扩散，看能扩散多远。

中心有两种情况：

• 回文子串是奇数时，中心是字母，比如 abcba ，这种要从下标 0,0 开始
• 回文子串是偶数时，中心是字母间隙，比如 abba ，这种要从下标 0,1 开始

Java 实现

    public String longestPalindrome(String s) {
        if (s == null || "".equals(s)){
            return s;
        }
        int start = 0;
        int end = 0;
        for (int i = 0; i < s.length(); i++){
            // 奇数情况，中点是字母 aba
            int len1 = expand(s, i, i);
            // 偶数情况，中点是间隙 bb
            int len2 = expand(s, i, i+1);
            int len = Math.max(len1, len2);
            if (len > end - start){
                start = i - (len-1)/2;
                end = i + len/2;
            }
        }
        // substring 方法是左闭右开
        return s.substring(start, end+1);
    }

    private int expand(String s, int left, int right){
        while (left >= 0 
        && right < s.length()
        && s.charAt(left) == s.charAt(right)){
                left--;
                right++;
        }

        // 跳出循环时，left 和 right 已经不满足回文条件了（多走了一步）
        return (right - 1) - (left + 1) + 1;
    }