求最长回文子串。

核心回答

可以用中心扩展法：回文子串关于中心对称，枚举每个字符作为奇数长度回文的中心，再枚举相邻字符之间的位置作为偶数长度回文的中心。每次从中心向两边比较，相等就继续扩展，遇到不相等或越界时停止，并记录最长区间。

这样不会漏掉奇数或偶数回文。最坏有 O(n) 个中心，每个中心扩展 O(n) 次，因此时间为 O(n²)；只记录下标和长度，额外工作空间为 O(1)，最终返回字符串所需空间另计。

例如 babad 可以返回 bab 或 aba；cbbd 应返回 bb，只检查单字符中心会漏掉这种偶数长度答案。题目要求连续子串，不能通过跳过中间字符拼出回文子序列。

Python 实现

def longest_palindrome(s: str) -> str:
    n = len(s)
    best_start = 0
    best_length = 0

    def expand(left: int, right: int) -> tuple[int, int]:
        while left >= 0 and right < n and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - left - 1

    for center in range(n):
        for left, right in ((center, center), (center, center + 1)):
            start, length = expand(left, right)
            if length > best_length:
                best_start = start
                best_length = length

    return s[best_start : best_start + best_length]

expand 返回起点和长度，比较过程中不构造子串；最后只切片一次。这里空字符串返回空串，同长答案保留先找到的一个。

扩展停止后，区间为什么这样算

以 cbbd 中间的两个 b 为例，初始左右下标为 1、2。两边相等，扩展到 0、3 时遇到 c 与 d 不相等，停止。

停止时左右指针已经位于有效回文区间外面，所以有效区间是闭区间 [left + 1, right - 1]，长度为 right - left - 1。对应本例起点 1、长度 2，正好取得 bb。停止原因如果是越界，也使用同一套计算。

任意非空回文都有一个字符中心或一个字符间隙中心。算法枚举这些中心，并对每个中心一直扩展到不能再扩展；因此最长回文对应的中心一定被处理，最终取最大长度就能得到答案。

为什么最坏是平方时间

像全部字符都相同的字符串，许多中心都能扩展很远，总比较次数达到 O(n²)。只看外面的一层循环，会漏掉内部扩展的成本。

代码没有保存每个中心的结果，也没有在循环中复制长子串，因此额外工作空间为 O(1)。Python 最后返回长度为 L 的切片，通常还需要 O(L) 的结果空间和复制时间；这不改变整体 O(n²) 的最坏时间上界。

动态规划与 Manacher 怎样比较

动态规划可以令 dp[left][right] 表示区间是否回文：两端相等，并且内部区间是回文时，当前区间才成立；长度为 1 或 2 的区间单独处理边界。按短区间到长区间计算，或者让左端从大到小遍历，保证内部状态已经求出。常规二维表时间和空间均为 O(n²)。

中心扩展利用了回文的结构，通常更容易写成少量工作变量。若进一步要求线性时间，可用 Manacher：维护已经找到的最右回文边界，利用对称中心的半径跳过已知匹配，再只比较尚未知的部分。它达到 O(n) 时间，通常需要 O(n) 半径数组，边界和奇偶定义也更复杂。

普通滑动窗口的单向收缩规则不适合直接套在本题上：一个区间不是回文，不代表加入更多字符后仍不可能变为回文，不能随意丢掉候选起点。

边界样例

assert longest_palindrome("") == ""
assert longest_palindrome("a") == "a"
assert longest_palindrome("ac") == "a"
assert longest_palindrome("cbbd") == "bb"
assert longest_palindrome("babad") == "bab"
assert longest_palindrome("aaaa") == "aaaa"
assert longest_palindrome("上海海上") == "上海海上"
assert longest_palindrome("🙂a🙂") == "🙂a🙂"

实现按 Python 的 Unicode 码点比较，区分大小写，空格和标点也参与匹配。若题目要求忽略这些字符，或按组合字形判断，需要先约定转换与分割规则；转换后还要保留位置映射，才能返回原字符串中的正确区间。

参考资料