5. 最长回文子串

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

示例 1：

输入: “babad” 输出: “bab” 注意: “aba” 也是一个有效答案。 示例 2：

输入: “cbbd” 输出: “bb”

由一个点向两边移动判断两边依次相等，或两个点相同然后向两边移动判断两边依次相等

public class LongestPalindrome {
    public String longestPalindrome(String s) {
        if (s.length() == 0) {
            return s;
        }
        int start = 0;
        int end = 0;
        for (int i = 0; i < s.length(); i++) {
            //一个点向两侧移动
            int length1 = length(s, i, i);
            //两个点向两侧移动
            int length2 = length(s, i, i + 1);
            int length = Math.max(length1, length2);
            if (length > end - start) {
                //两点移动时，结果为偶数，i为左侧的数，i+1为右侧的数，因此i左侧只有3个数，右侧4个数
                //一个点移动结果为奇数，减一不影响
                start = i - (length - 1) / 2;
                end = i + length / 2;
            }
        }
        return s.substring(start, end + 1);
    }
    private int length(String s, int left, int right){
        //找出最大子串长度
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}