What is the main pattern used in Longest Palindromic Substring?

The primary pattern is state transition dynamic programming, which uses previously computed palindromes to efficiently find larger ones and track expansions.

How do I handle both odd and even length palindromes?

Treat each character as a center for odd-length palindromes and each pair of adjacent characters as a center for even-length palindromes, expanding outwards from each center.

Can this approach handle strings up to 1000 characters efficiently?

Yes, by combining two-pointer expansion with DP state reuse, the solution maintains O(n) time and O(n) space complexity, making it efficient for maximum constraints.

What are common mistakes when implementing this problem?

Common pitfalls include forgetting even-length palindromes, misinitializing DP base cases, and expanding pointers beyond string boundaries causing errors.

How does the DP state transition work here?

The DP table tracks whether substring s[i..j] is a palindrome using dp[i+1][j-1] and character matches, allowing previously found palindromes to inform longer substring checks efficiently.

#5

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

最长回文子串

给你一个字符串 s ，找到 s 中最长的回文子串。示例 1：输入： s = "babad" 输出： "bab" 解释： "aba" 同样是符合题意的答案。示例 2：输入： s = "cbbd" 输出： "bb" 提示： 1 s 仅由数字和英文字母组成

双指针字符串动态规划

题目描述

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

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示字符串 $s[i..j]$ 是否为回文串，初始时 $f[i][j] = true$ 。

接下来，我们定义变量 $k$ 和 $mx$ ，其中 $k$ 表示最长回文串的起始位置， $mx$ 表示最长回文串的长度。初始时 $k = 0$ , $mx = 1$ 。

考虑 $f[i][j]$ ，如果 $s[i] = s[j]$ ，那么 $f[i][j] = f[i + 1][j - 1]$ ；否则 $f[i][j] = false$ 。如果 $f[i][j] = true$ 并且 $mx \lt j - i + 1$ ，那么我们更新 $k = i$ , $mx = j - i + 1$ 。

由于 $f[i][j]$ 依赖于 $f[i + 1][j - 1]$ ，因此我们需要保证 $i + 1$ 在 $j - 1$ 之前，因此我们需要从大到小地枚举 $i$ ，从小到大地枚举 $j$ 。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 是字符串 $s$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        f = [[True] * n for _ in range(n)]
        k, mx = 0, 1
        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                f[i][j] = False
                if s[i] == s[j]:
                    f[i][j] = f[i + 1][j - 1]
                    if f[i][j] and mx < j - i + 1:
                        k, mx = i, j - i + 1
        return s[k : k + mx]

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Do you identify both odd and even length palindromes during center expansion?
question_mark
Can you explain how previously computed palindromes reduce redundant checks in the DP table?
question_mark
Will you update the longest palindrome tracking correctly when multiple candidates of the same length exist?

warning

常见陷阱

外企场景

error
Forgetting to check even-length palindromes, which requires treating centers between characters.
error
Not initializing DP base cases correctly, leading to incorrect longer palindrome computation.
error
Expanding beyond string bounds when checking centers, causing runtime errors.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the number of distinct palindromic substrings in a given string.
arrow_right_alt
Return the longest palindromic subsequence instead of substring, allowing non-contiguous characters.
arrow_right_alt
Compute the longest palindrome in a streaming string with limited memory, requiring on-the-fly updates.

help

常见问题

外企场景

继续练习

#647 回文子串 #22 括号生成 #32 最长有效括号