5.最长回文子串

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

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

示例 2：

输入：s = “cbbd”
输出：”bb”

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

题解：

class Solution {
    public String longestPalindrome(String s) {
        if (s.length() < 2) {
            return s;
        }
        int left = 0;
        int right = 0;
        int max = 0;
        int maxStart = 0;
        /**
            对于每个字符都采取中心扩散来查找最长回文子串
            先往左找，如果左边的字符跟当前字符一致则更新回文子串的长度，往右找同理
            左右找完后再同时往左右两边扩散查找，如果两边字符一致则当前记录的回文子串长度+=2
            比较最长的会问字串长度，如果是最长的就更新该回文子串的最左字符开始位置
         */
        for (int i = 0; i < s.length(); i++) {
            int len = 1;
            left = i - 1;
            right = i + 1;
            while (left >= 0 && s.charAt(left) == s.charAt(i)) {
                left--;
                len++;
            }
            while (right < s.length() && s.charAt(right) == s.charAt(i)) {
                right++;
                len++;
            }
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                len += 2;
                left--;
                right++;
            }
            if (len > max) {
                max = len;
                maxStart = left;
            }
        }
        return s.substring(maxStart + 1, maxStart + max + 1);
    }
}