最长回文子串 图解题解

这道题到底在问什么

s

"babad"

输出

"bab"（或 "aba"，都对，长度 3）

先想最直接的笨办法

最直接的笨办法：枚举起点和终点(n² 个子串)，每个子串再花 O(n) 判断是否回文，合起来 O(n³)。换个思路：回文一定有个中心，从中心往两边扩，能省一个量级。（动画第 3 步）

最优解：一步一步想明白

1. 3最直接的笨办法：枚举起点和终点(n² 个子串)，每个子串再花 O(n) 判断是否回文，合起来 O(n³)。换个思路：回文一定有个中心，从中心往两边扩，能省一个量级。
2. 4为什么成立：回文关于中心镜像对称，知道中心就能向外验证。对每个中心，l、r 一起向外走，只要 s[l]==s[r] 就继续扩；一旦不等或越界就停。中心有两种——单字符(奇回文)和两字符之间(偶回文)，都试一遍取最长。
3. 5center=1 l=r=1从中心 a(下标 1)开始，l=r=1。单字符本身就是回文，作为起点向两边扩。
4. 6l=0 r=2 b==bl 退到 0(b)、r 进到 2(b)，s[0]==s[2]，扩成功！当前回文 "bab"、长度 3，刷新最长记录。继续往外扩。
5. 7l=-1 越界 停转折：l 再退一步就到 −1 越界，扩展终止。以 a 为奇中心扩出的最长回文是 "bab"(长度 3)。换下一个中心。
6. 8l=0 r=1 b≠a试偶中心(下标 0、1 之间)：l=0 是 b、r=1 是 a，s[0]≠s[1]，第一步就不相等，一次都没扩成，这个偶中心贡献长度 0。这就是负例：不等立刻停。但偶中心也能扩成功——换个串看正例。
7. 9l=1 r=2 b==b ✓换个迷你串 "abba" 看偶中心扩成功：偶中心从两字符之间起步，l=1、r=2，s[1]==s[2](b==b)，第一步就成回文 "bb"(长度 2)。这正是奇中心做不到的——单字符中心起步长度只能是奇数。继续往外扩。
8. 10l=0 r=3 a==a ✓l 退到 0(a)、r 进到 3(a)，s[0]==s[3]，扩成功！偶回文 "abba"(长度 4)整个扩出来了。再走 l 就到 −1 越界、停。这就是亲眼看见 (i,i+1) 偶中心也能扩出东西——和奇中心 bab/aba 形成对照。
9. 11center=2 l=r=2再换中心：以下标 2 的 b 为奇中心，l=r=2，单字符回文起步，向两边扩。
10. 12l=1 r=3 a==al 退到 1(a)、r 进到 3(a)，s[1]==s[3]，扩成功！回文 "aba"、长度 3，和当前最长打平。继续扩。
11. 13l=0 r=4 b≠d继续扩到 l=0(b)、r=4(d)，s[0]≠s[4]，不相等，扩展停止。以 b 为中心扩出的最长仍是 "aba"(长度 3)。
12. 14停时 l=0 r=4 → 取 [l+1,r-1]=[1,3]最容易错的一格：while 跳出时，l、r 已经各多走一步、踩在了不等的 b 和 d 上。所以真正的回文不是 [l, r]，而是收回一格的 [l+1, r-1]，也就是下标 1 到 3 的 "aba"。记住这个 ＋1／−1。
13. 15best=3 "bab"/"aba"把每个奇中心、偶中心都扩一遍：最长是 "bab" 和 "aba"，长度都为 3。返回其一即可。
14. 18抓住"回文关于中心对称"这一点，就把"枚举子串 + 判回文"两件事并成一件：从中心往外扩，扩到哪算到哪。回文子串计数(647)、最长回文子序列(516)都和它同源。
15. 23把这题练到能复述后，再去同类题里迁移：先复用 expand 骨架，再调整边界条件。卡壳时点右下角问问小欧 AI 私教，让它陪你把 647 的"累加"改法推一遍。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def longestPalindrome(self, s):
        ans_l = ans_r = 0
        def expand(l, r):
            while l >= 0 and r < len(s) and s[l] == s[r]:
                l -= 1
                r += 1
            return l + 1, r - 1
        for i in range(len(s)):
            for l, r in (expand(i, i), expand(i, i + 1)):
                if r - l > ans_r - ans_l:
                    ans_l, ans_r = l, r
        return s[ans_l:ans_r + 1]

class Solution {
public:
    string longestPalindrome(string s) {
        int al = 0, ar = 0;
        for (int i = 0; i < (int)s.size(); i++)
            for (int j = 0; j < 2; j++) {
                int l = i, r = i + j;
                while (l >= 0 && r < (int)s.size() && s[l] == s[r]) { l--; r++; }
                l++; r--;
                if (r - l > ar - al) { al = l; ar = r; }
            }
        return s.substr(al, ar - al + 1);
    }
};

class Solution {
    public String longestPalindrome(String s) {
        int al = 0, ar = 0;
        for (int i = 0; i < s.length(); i++)
            for (int j = 0; j < 2; j++) {
                int l = i, r = i + j;
                while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
                l++; r--;
                if (r - l > ar - al) { al = l; ar = r; }
            }
        return s.substring(al, ar + 1);
    }
}

# 骨架：一个 expand + 每位置试奇偶两种中心
def expand(l, r):           # 传入初始左右指针
    while l >= 0 and r < n and s[l] == s[r]:  # 两边相等就扩
        l -= 1; r += 1
    return r - l - 1        # 收一格后的回文长度
for i in range(n):
    odd  = expand(i, i)     # 奇中心: 单字符
    even = expand(i, i + 1) # 偶中心: 两字符之间
    best = max(best, odd, even)   # 按需求改这里

// 骨架：expand 返回"以(l,r)为中心的回文长度"
auto expand = [&](int l, int r) {
    while (l >= 0 && r < n && s[l] == s[r]) { l--; r++; }
    return r - l - 1;        // 收一格后的回文长度
};
for (int i = 0; i < n; i++) {
    int odd  = expand(i, i);      // 奇中心
    int even = expand(i, i + 1);  // 偶中心
    best = max({best, odd, even}); // 按需求改这里
}

// 骨架：expand 返回"以(l,r)为中心的回文长度"
int expand(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
    return r - l - 1;        // 收一格后的回文长度
}
for (int i = 0; i < n; i++) {
    int odd  = expand(s, i, i);      // 奇中心
    int even = expand(s, i, i + 1);  // 偶中心
    best = Math.max(best, Math.max(odd, even)); // 按需求改这里
}

复杂度

面试官可能追问