最长回文子串问题

题目描述：给定一个字符串s，找到s中最长的回文子串。回文串是指正着读和反着读都一样的字符串。

解题过程：

1. 问题理解
   回文子串需要满足：从中心向两边扩展时，两边的字符完全对称。例如"aba"是回文，"abba"也是回文。我们需要找到给定字符串中最长的这样的连续子串。

2. 暴力解法（基础思路）
   最简单的思路是检查所有可能的子串：

• 枚举所有起始位置i和结束位置j（i ≤ j）
• 检查子串s[i...j]是否是回文
• 记录最长的回文子串

时间复杂度：O(n³)，其中检查回文需要O(n)，总共有O(n²)个子串。

3. 中心扩展法（优化解法）
   观察回文的对称性质，每个回文都有一个中心：

• 奇数长度回文：中心是一个字符（如"aba"的中心是'b'）
• 偶数长度回文：中心是两个相同字符之间（如"abba"的中心在两个'b'之间）

算法步骤：

1. 遍历字符串的每个位置，作为可能的中心
2. 对于每个中心，向两边扩展，直到不再满足回文条件
3. 记录找到的最长回文子串

具体实现：

def longestPalindrome(s):
    def expandAroundCenter(left, right):
        # 从中心向两边扩展
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        # 返回回文子串的起始和结束位置
        return left + 1, right - 1
    
    start, end = 0, 0
    for i in range(len(s)):
        # 奇数长度回文，中心为单个字符
        left1, right1 = expandAroundCenter(i, i)
        # 偶数长度回文，中心为两个相同字符之间
        left2, right2 = expandAroundCenter(i, i + 1)
        
        # 更新最长回文
        if right1 - left1 > end - start:
            start, end = left1, right1
        if right2 - left2 > end - start:
            start, end = left2, right2
    
    return s[start:end+1]

时间复杂度：O(n²)，空间复杂度：O(1)

4. 动态规划法（另一种思路）
   定义dp[i][j]表示子串s[i...j]是否是回文：

• 基本情况：单个字符一定是回文（dp[i][i] = true）
• 两个相同字符是回文（dp[i][i+1] = true if s[i] == s[i+1]）
• 状态转移：dp[i][j] = true 当且仅当 s[i] == s[j] 且 dp[i+1][j-1] = true

这种方法也是O(n²)时间复杂度，但需要O(n²)空间。

5. 马拉车算法（Manacher's Algorithm）
   更高级的算法，时间复杂度O(n)，但实现较复杂。核心思想是利用已知的回文信息来避免重复计算。

总结：中心扩展法是面试中最实用的解法，兼顾了效率和实现难度。