最长回文子串

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

示例 1：

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

示例 2：

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

https://leetcode.cn/problems/longest-palindromic-substring/description/

中心扩散法

回文串是中心对称的，如果我们枚举每一个可能的“回文中心”，然后用双指针向左右两边同步扩散，直到左右字符不相等为止

回文串的长度可能是奇数（中心是 1 个字符，如 "aba" 中心是 'b'），也可能是偶数（中心是 2 个字符之间的缝隙，如 "abba" 中心是 "bb"）。因此每个位置 i 需要分别以 (i, i) 和 (i, i + 1) 作为中心扩散两次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public String longestPalindromeCenter(String s) {
    if (s == null || s.length() < 2) return s;
    int start = 0, maxLen = 1;

    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);     // 奇数长度回文：以 s[i] 为中心
        int len2 = expandAroundCenter(s, i, i + 1); // 偶数长度回文：以 s[i] 和 s[i+1] 为中心
        int len = Math.max(len1, len2);
        
        if (len > maxLen) {
            maxLen = len;
            // 根据中心 i 和最大长度 len 反推子串起点下标
            start = i - (len - 1) / 2;
        }
    }
    return s.substring(start, start + maxLen);

}

private int expandAroundCenter(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    // 跳出循环时 s[left] != s[right]，实际回文区间是 [left + 1, right - 1]
    // 长度为 (right - 1) - (left + 1) + 1 = right - left - 1
    return right - left - 1;
}