5. 最长回文子串

LeetCode 5¹ · 中等 · 多维动态规划

题

给字符串 s，返回其中最长的回文子串（连续、正读反读一样）。有多个同长的，返回任意一个。

例：s = "babad" → "bab"（"aba" 也对）；s = "cbbd" → "bb"。

一句话

每个回文都有中心——单字符或两字符之间；枚举所有中心向两边扩，扩不动时记录长度。

关键技巧

区间 DP：状态是区间两端。

状态：\(f(i,j)\) = s[i..j] 是否回文。
转移：\(f(i,j) = (s_i = s_j) \wedge \big(j - i < 2 \vee f(i+1,j-1)\big)\)。
初值：长度 1 为真；长度 2 看两字符是否相等（已含在 \(j - i < 2\) 里）。
顺序：\(f(i,j)\) 依赖 \(f(i+1,j-1)\)——左下角，所以 \(i\) 从大到小、\(j\) 从小到大，或按区间长度递增。遍历顺序由依赖方向决定，这是区间 DP 最容易写错的地方。

中心扩展：同样的依赖，换个方向走。 DP 表里 \(f(i,j)\) 只依赖 \(f(i+1,j-1)\)，依赖链是一条条从中心往外的斜线。沿斜线从中心出发往外走，一旦不等就停——后面的更长区间不可能是回文。每条斜线独立，所以不需要存表。

中心有 \(2n - 1\) 个：\(n\) 个单字符（奇数长）+ \(n - 1\) 个缝隙（偶数长）。
用 expand(l, r) 统一两种：奇数传 (i, i)，偶数传 (i, i+1)。

更快（知道即可）。 Manacher 算法利用已知回文的对称性复用半径，\(O(n)\)。

解

中心扩展区间 DP

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(l: int, r: int) -> tuple[int, int]:
            while l >= 0 and r < len(s) and s[l] == s[r]:
                l, r = l - 1, r + 1
            return l + 1, r  # 回文是 s[l+1:r]

        lo, hi = 0, 1
        for i in range(len(s)):
            for l, r in (expand(i, i), expand(i, i + 1)):  # 奇、偶两种中心
                if r - l > hi - lo:
                    lo, hi = l, r
        return s[lo:hi]

时间 \(O(n^2)\)，空间 \(O(1)\)。

class Solution2:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        f = [[False] * n for _ in range(n)]
        lo, hi = 0, 1
        for i in range(n - 1, -1, -1):      # i 倒序：f[i][j] 依赖 f[i+1][j-1]
            for j in range(i, n):
                if s[i] == s[j] and (j - i < 2 or f[i + 1][j - 1]):
                    f[i][j] = True
                    if j + 1 - i > hi - lo:
                        lo, hi = i, j + 1
        return s[lo:hi]

时间 \(O(n^2)\)，空间 \(O(n^2)\)。提交时类名改回 Solution。

延伸

回文判定表复用：131. 分割回文串先建同一张 \(f(i,j)\) 表，再回溯切分。
回文子序列（LeetCode 516）：不要求连续，转移变成 \(s_i = s_j\) 时 \(f(i+1,j-1) + 2\)，否则 \(\max(f(i+1,j), f(i,j-1))\)——等价于 s 与 reverse(s) 的 1143. 最长公共子序列。
坑：别用「s 与反转串的最长公共子串」——"abacdfgdcaba" 会得到不是回文的 "abacd"。

自测

for S in (Solution, Solution2):
    s = S()
    assert s.longestPalindrome("babad") in ("bab", "aba")
    assert s.longestPalindrome("cbbd") == "bb"
    assert s.longestPalindrome("a") == "a"
    assert s.longestPalindrome("ac") in ("a", "c")
    assert s.longestPalindrome("forgeeksskeegfor") == "geeksskeeg"

LeetCode 5，2026-09-29 读。 ↩