5 最长回文子串

一、题目

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


二、题解

思路：中心扩展法 (Two Pointers)

回文串的一个重要特性就是对称性。如果我们从它的中心向两边展开，两边的字符一定是相同的。因此，我们可以将字符串中的每一个字符（或两个字符的间隙）视为潜在的“回文中心”，然后使用双指针向左右两边扩展，直到字符不匹配为止。

这里有一个细节需要注意：回文串的长度可能是奇数，也可能是偶数。

• 奇数长度： 中心是一个字符，例如 "aba" 的中心是 'b'。
• 偶数长度： 中心是两个字符之间的间隙，例如 "abba" 的中心是两个 'b' 之间。

算法步骤：

1. 遍历字符串 s 的每一个下标 i。
2. 以 s[i] 为中心，利用双指针向外扩展，寻找最长的奇数长度回文子串。
3. 以 s[i] 和 s[i+1] 为中心，利用双指针向外扩展，寻找最长的偶数长度回文子串。
4. 比较奇数和偶数情况下的最长长度，并更新全局记录的最大长度以及对应的起始和结束下标。
5. 遍历结束后，根据记录的下标截取并返回最终的子串。

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }

        // 记录最长回文子串的起始和结束位置
        int start = 0, end = 0;

        for (int i = 0; i < s.length(); i++) {
            // 情况一：回文串长度为奇数，以当前字符 s[i] 为中心
            int len1 = expandAroundCenter(s, i, i);
            // 情况二：回文串长度为偶数，以 s[i] 和 s[i+1] 为中心
            int len2 = expandAroundCenter(s, i, i + 1);

            // 取两种情况下的最大回文长度
            int len = Math.max(len1, len2);

            // 如果找到了更长的回文子串，更新起止位置
            if (len > end - start) {
                // 根据中心点 i 和总长度 len，推算出边界
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }

        // 根据计算出的起止位置截取子串（注意 substring 的右边界是开区间）
        return s.substring(start, end + 1);
    }

    // 辅助方法：以 left 和 right 为中心，向两边扩展，返回能够扩展的最大长度
    private int expandAroundCenter(String s, int left, int right) {
        // 当左指针没有越界，右指针没有越界，且左右字符相等时，继续扩展
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        // 退出循环时，left 和 right 指向的字符已经不相等了
        // 所以实际的回文串边界是 (left + 1) 到 (right - 1)
        // 长度为 (right - 1) - (left + 1) + 1 = right - left - 1
        return right - left - 1;
    }
}

时间复杂度：$O(n^2)$

空间复杂度：$O(1)$