最长回文子串（Longest Palindromic Substring）

最长回文子串

题目描述

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

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

解题思路

核心观察

回文串的中心可以是单个字符（奇数长度，如 “aba”）或两个相邻字符（偶数长度，如 “bb”）。从中心向两端扩展，直到不再是回文串。

算法步骤

1. 对每个可能的中心点进行扩展
2. 奇数中心：以 s[i] 为中心向两边扩展
3. 偶数中心：以 s[i] 和 s[i+1] 为中心向两边扩展
4. 比较更新最长回文子串的起止位置

代码实现

import sys

s = sys.stdin.readline().strip()

def fun(s, l, r):
    while l >= 0 and r < len(s) and s[l] == s[r]:
        l -= 1
        r += 1
    return l + 1, r - 1

start, end = 0, 0
for i in range(len(s)):
    l1, r1 = fun(s, i, i)
    l2, r2 = fun(s, i, i + 1)
    if r1 - l1 > end - start:
        start, end = l1, r1
    if r2 - l2 > end - start:
        start, end = l2, r2

print(s[start: end + 1])

代码解析

• fun(s, l, r)：以 l, r 为中心扩展，返回回文串的起止位置
• 奇数中心 (i, i)：处理 “aba” 类型
• 偶数中心 (i, i+1)：处理 “abba” 类型

时间复杂度

• 每个位置作为中心最多扩展 O(n)
• 总计：O(n²)