5.最长回文子串
dp, two pointers, string, https://leetcode.cn/problems/longest-palindromic-substring/
给你一个字符串 s，找到 s 中最长的
回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。示例 2：
输入：s = "cbbd"
输出："bb"提示：
1 <= s.length <= 1000s仅由数字和英文字母组成
思路：对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。使用右上三角 DP，只有 left ≤ right（右上三角）才有效。
状态：dp[i][j]表示子串s[i:j+1]是否为回文子串
状态转移方程：dp[i][j] = dp[i+1][j-1] ∧ (S[i] == s[j])
动态规划中的边界条件，即子串的长度为 1 或 2。对于长度为 1 的子串，它显然是个回文串；对于长度为 2 的子串，只要它的两个字母相同，它就是一个回文串。
步骤：
- 构造
is_palindrome[left][right] - “按 right 列生成”二维表
- 最长回文子串直接在 DP 表里查即可。用双指针遍历所有区间，在布尔表上查即可。
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n <= 1:
return s
# ---------- 第一部分：预处理所有回文子串（DP） ----------
is_palindrome = [[False] * n for _ in range(n)]
for right in range(n):
for left in range(right + 1):
if s[left] == s[right] and (right - left <= 1 or is_palindrome[left + 1][right - 1]):
is_palindrome[left][right] = True
# ---------- 第二部分：扫描所有 (left, right) 求最长 ----------
max_len = 1
start = 0
for left in range(n):
for right in range(left, n):
if is_palindrome[left][right] and (right - left + 1) > max_len:
max_len = right - left + 1
start = left
return s[start:start + max_len]🔍 形象化理解
is_palindrome[left][right]表示s[left:right+1]是否为回文- “右上三角”按列填充
- 依赖关系在左下
(left+1, right-1) - 这样保证依赖已计算
right →
0 1 2 3 4 ...
l 0 ■ ■ ■ ■ ■
e 1 ■ ■ ■ ■
f 2 ■ ■ ■
t 3 ■ ■
↓ 4 ■📝 时间复杂度
- DP 构造：O(n²)
- 扫描最长：O(n²)
- 总复杂度：O(n²)，满足 n ≤ 1000 要求
如果你愿意，我还可以给你：
- 中心扩展版本（更快更常用）
- Manacher 线性算法版本（O(n)）
逐列展示（按 right 列填充）的示例，帮助完全理解“右上三角 DP 按列生成”。
示例字符串：
s = "babad" 0 1 2 3 4 b a b a dDP 表：
is_palindrome[left][right]其中只有 left ≤ right（右上三角）才有效。✅ 按列填充（固定 right，从上到下填 left）
下面逐列展示 “right = 0, 1, 2, ...” 时每一列是怎么被填出来的。
📌 第 0 列：right = 0
检查所有
left = 0..0
left right substring s[left]==s[right]? 长度<=2? 结果 0 0 "b" ✔ ✔ True DP 表（T = True, . = False）：
r→ 0 1 2 3 4 l↓ 0 T . . . . 1 . . . . . 2 . . . . . 3 . . . . . 4 . . . . .📌 第 1 列：right = 1（检查 left = 0..1）
- left = 0, right = 1 → "ba"
- s[0] != s[1] → False
- left = 1, right = 1 → "a"
- 单字符 → True
DP 表：
r→ 0 1 2 3 4 l↓ 0 T . . . . 1 . T . . . 2 . . . . . 3 . . . . . 4 . . . . .📌 第 2 列：right = 2（检查 left = 0..2）
- left = 0, right = 2 → "bab"
- s[0] == s[2]
- (right - left > 1) → 看
is_palindrome[1][1]is_palindrome[1][1] = True→ 整段为 True
- left = 1, right = 2 → "ab"
- s[1] != s[2] → False
- left = 2, right = 2 → "b"
- 单字符 → True
DP 表：
r→ 0 1 2 3 4 l↓ 0 T . T . . 1 . T . . . 2 . . T . . 3 . . . . . 4 . . . . .📌 第 3 列：right = 3（检查 left = 0..3）
- left = 0 → "baba"
- s[0] != s[3] → False
- left = 1 → "aba"
- s[1] == s[3]
- 需要
is_palindrome[2][2] = True→ True
- left = 2 → "ba"
- s[2] != s[3] → False
- left = 3 → "a"
- True
DP 表：
r→ 0 1 2 3 4 l↓ 0 T . T . . 1 . T . T . 2 . . T . . 3 . . . T . 4 . . . . .📌 第 4 列：right = 4（检查 left = 0..4）
- left = 0 → "babad"
- s[0] != s[4] → False
- left = 1 → "abad"
- s[1] != s[4] → False
- left = 2 → "bad"
- s[2] != s[4] → False
- left = 3 → "ad"
- s[3] != s[4] → False
- left = 4 → "d"
- True
最终 DP 表：
r→ 0 1 2 3 4 l↓ 0 T . T . . 1 . T . T . 2 . . T . . 3 . . . T . 4 . . . . T🔍 如何看出最长回文？
从表中找 True 中最长区间：
- (0,2) → "bab" 长度 3
- (1,3) → "aba" 长度 3
最长回文 = "bab" 或 "aba"
🎯 总结：为什么要按列填？
因为：
is_palindrome[left][right]依赖is_palindrome[left+1][right-1]
Plan
- Initialize a 2D list
dpwheredp[i][j]will beTrueif the substrings[i:j+1]is a palindrome. - Iterate through the string in reverse order to fill the
dptable. - For each character, check if the substring is a palindrome by comparing the characters at the ends and using the previously computed values in
dp. - Keep track of the start and end indices of the longest palindromic substring found.
- Return the substring defined by the start and end indices.
对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。
状态：dp[i][j]表示子串s[i:j+1]是否为回文子串
状态转移方程：dp[i][j] = dp[i+1][j-1] ∧ (S[i] == s[j])
动态规划中的边界条件，即子串的长度为 1 或 2。对于长度为 1 的子串，它显然是个回文串；对于长度为 2 的子串，只要它的两个字母相同，它就是一个回文串。
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n == 0:
return ""
# Initialize the dp table
dp = [[False] * n for _ in range(n)]
start, max_length = 0, 1
# Every single character is a palindrome
for i in range(n):
dp[i][i] = True
# Check for palindromes of length 2
for i in range(n - 1):
if s[i] == s[i + 1]:
dp[i][i + 1] = True
start = i
max_length = 2
# Check for palindromes of length greater than 2
for length in range(3, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j] and dp[i + 1][j - 1]:
dp[i][j] = True
start = i
max_length = length
return s[start:start + max_length]
if __name__ == "__main__":
sol = Solution()
print(sol.longestPalindrome("babad")) # Output: "bab" or "aba"
print(sol.longestPalindrome("cbbd")) # Output: "bb"Plan
- Initialize variables to store the start and end indices of the longest palindromic substring.
- Iterate through each character in the string, treating each character and each pair of consecutive characters as potential centers of palindromes.
- For each center, expand outwards while the characters on both sides are equal.
- Update the start and end indices if a longer palindrome is found.
- Return the substring defined by the start and end indices.
class Solution:
def longestPalindrome(self, s: str) -> str:
if not s:
return ""
start, end = 0, 0
for i in range(len(s)):
odd_len = self.expandAroundCenter(s, i, i)
even_len = self.expandAroundCenter(s, i, i + 1)
max_len = max(odd_len, even_len)
if max_len > end - start:
start = i - (max_len - 1) // 2
end = i + max_len // 2
return s[start:end + 1]
def expandAroundCenter(self, s: str, left: int, right: int) -> int:
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1
if __name__ == "__main__":
sol = Solution()
print(sol.longestPalindrome("babad")) # Output: "bab" or "aba"
print(sol.longestPalindrome("cbbd")) # Output: "bb"
这个双指针是从中间往两边跑。
- 当退出循环时，
[left+1, right-1]是最后一个有效的回文区间。 - 回文长度 =
(right - 1) - (left + 1) + 1 = right - left - 1
时间复杂度：O(n²)：外层循环 O(n)，每次扩展最坏 O(n)
Manacher算法
class Solution:
def expand(self, s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return (right - left - 2) // 2
def longestPalindrome(self, s: str) -> str:
end, start = -1, 0
s = '#' + '#'.join(list(s)) + '#'
arm_len = []
right = -1
j = -1
for i in range(len(s)):
if right >= i:
i_sym = 2 * j - i
min_arm_len = min(arm_len[i_sym], right - i)
cur_arm_len = self.expand(s, i - min_arm_len, i + min_arm_len)
else:
cur_arm_len = self.expand(s, i, i)
arm_len.append(cur_arm_len)
if i + cur_arm_len > right:
j = i
right = i + cur_arm_len
if 2 * cur_arm_len + 1 > end - start:
start = i - cur_arm_len
end = i + cur_arm_len
return s[start+1:end+1:2]
在大回文 [L, R] 内部，左右完全对称，所以 i_sym 的回文结构会被“复制”到 i 的位置——只要不超出边界 R。
这段代码是用于解决“最长回文子串”问题的一个Python实现。它使用了Manacher算法的变种，通过在每个字符间插入特殊字符（这里是
#）来处理奇数和偶数长度的回文字符串。让我们逐段解析这个解决方案：扩展函数
expand
- 此函数尝试从给定的中心点向两边扩展，以找到以该中心点为中心的最大回文半径。
- 如果左右指针指向的字符相等且都在字符串范围内，则继续向外扩展。
- 返回值为最大回文半径，即
(right - left - 2) // 2。主函数
longestPalindrome
- 首先，将原始字符串
s转换成一个新字符串，其中每个字符之间都插入了一个#，这样可以确保所有可能的回文子串都是奇数长度，便于处理。end和start变量用于记录最长回文子串的边界。arm_len列表存储每个位置的回文臂长。right和j分别表示当前已知最右端的回文子串的右边界及其对应的中心点。- 在遍历新字符串时，如果当前索引
i位于right内，那么利用对称性，计算出i关于j的对称点i_sym，并确定最小臂长。- 使用
expand函数计算当前位置的实际臂长，并更新arm_len列表。- 如果当前臂长加上
i超过了right，则更新right和j。- 如果当前找到的回文子串比之前记录的更长，则更新
start和end。- 最后，返回原始字符串中对应最长回文子串的部分，注意去掉添加的
#符号。整个算法的核心思想是利用已经计算过的回文信息来减少重复计算，从而提高效率。这种方法的时间复杂度接近O(n)，空间复杂度为O(n)。
min_arm_len = min(arm_len[i_sym], right - i) 如何理解？
min_arm_len = min(arm_len[i_sym], right - i)这一行代码是用来确定从当前位置i开始进行中心扩展时，可以跳过的最小臂长。这里有两个关键点需要理解：
arm_len[i_sym]:
i_sym是位置i关于当前已知最右边回文子串中心j的对称点，计算方式为2 * j - i。arm_len[i_sym]表示的是对称点i_sym处的回文臂长。如果i_sym位置的回文臂长足够大，那么根据对称性，我们可以在i位置直接获得至少相同的臂长，因为这两个位置关于j对称。
right - i:
right是当前已知最右端回文子串的边界。right - i表示从位置i到当前已知最右端的距离。由于我们已经知道在right之前的字符都是回文的一部分，因此在i位置进行扩展时，我们至少可以达到right位置，而不需要重新验证这些字符。综合以上两点，
min_arm_len取两者中的较小值，确保了以下几点：
- 如果
i_sym位置的臂长小于或等于right - i，我们可以直接使用i_sym位置的臂长，因为它不会超出已知的回文区域。- 如果
i_sym位置的臂长大于right - i，则我们只能保证到right位置是回文，所以取right - i作为最小臂长。这样做的目的是为了减少不必要的重复计算，通过利用之前计算的结果（即
arm_len中的信息）来加速找到当前位置的最长回文臂长的过程。这实际上是Manacher算法中的一种优化手段，它允许我们在某些情况下快速跳过已经确认的部分，从而提高算法的整体效率。
思路：马拉车算法（Manacher）
首先一个比较基础的想法是研究以某一个位置为中心的回文串，但考虑到可能存在aba和aa这样不同奇偶性的回文串，将其补齐成类似#a#b#a#的形式，这样所有的回文串都是奇数。 然后，考虑某一个位置为中心的回文串，朴素的算法就是一步一步地扩大半径，直到不再回文，即这一部分代码
while 0 <= i - k and i + k < n and ns[i - k] == ns[i + k]:
k += 1而马拉车算法在这一部分朴素的算法之外，进一步考虑到在我找到这个位置最长的回文串的时候，我在后面的寻找过程中可以利用这个信息。
我们维护一个最右边的回文串的边界l, r，如果i已经超出了这一部分，那么就只能直接调用后面的朴素算法；否则，我们可以利用之前的信息，考察在目前的l, r下对称的那个点l+r-i的最长回文串，将其设为我们朴素算法的起始半径来进行循环。
特别地，如果对称过来的半径太长，超出了r的部分事实上我们目前还没进行研究，所以最大值只能到r-i-1。
每次求解之后更新最右的r以及对应的l。
朴素算法，时间复杂度O(n²); Manacher，时间复杂度O(n)。（while循环每进一次r至少变大1）
# 曹以楷 24物理学院
class Solution:
def longestPalindrome(self, s: str) -> str:
ns = f"#{'#'.join(s)}#"
n = len(ns)
# Manacher start
d = [0]*n
l, r = 0, -1
for i in range(n):
k = 1 if i > r else min(d[l + r - i], r - i + 1)
while 0 <= i - k and i + k < n and ns[i - k] == ns[i + k]:
k += 1
d[i] = k
k -= 1
if i + k > r:
l = i - k
r = i + k
# Manacher end
cnt = max(d)
idx = d.index(cnt)
return ns[idx-cnt+1:idx+cnt].replace("#", "")思路：
- 最开始我没看到题目要求子串必须连续！我想了很久，想到了可能要把原字符串逆序但不知道逆序之后干什么，然后一个同学告诉我直接求最长公共子序列就好，感觉瞬间明白了
- 然后发现子串要求连续，在原来程序的基础上，取出所有的公共子序列，再找其中既是回文的又是最长的那个，也算是过了
# 颜鼎堃 24工学院
class Solution:
def longestPalindrome(self, s: str) -> str:
t = "".join(reversed(s))
n = len(s)
strings = [["" for i in range(n + 2)] for j in range(n + 2)]
for i in range(n):
for j in range(n):
if s[i] == t[j]:
strings[i + 1][j + 1] = strings[i][j] + s[i]
pos_pal = set()
max_par = s[0]
for i in map(set, strings):
pos_pal |= i
for i in pos_pal:
if i and i == i[::-1]:
max_par = max(max_par, i, key=len)
return max_par
if __name__ == '__main__':
sol = Solution()
print(sol.longestPalindrome(input()))【李明阳 25生科学院】
动态规划法穷举，需要列举全部的子串逐个判断。注意到该题目对于程序内存有着极其严格的要求，因此使用滚动数组来存储结果 用l代表左边界，r代表又边界，闭区间[l,r]确定了字符串从index=l到index=r（包括两端点）这一子串。
①如果子串长度为1则一定为回文序列 ②子串长度为2则只需比较首尾两个字符 ③子串长度大于2时要求首尾相同，并且去掉首尾两个之后剩下的部分也应该是回文序列
如果用（l,r）代表一个子串，需要检查的情况可以列为下面的表格，箭头表示递归的方向。为了一次遍历解决问题，显然应该自下而上遍历。接下来的问题是如何处理以上①②③三种不同情形下的状态转移方程： 我们在开始时就把最长回文串设置为第一个字母，长度为1，这样可以避免列举情况① 注意到表格中蓝色方块的位置没有定义，如果补充定义为True，即可统一②③两种情况。所有l=r的情况也应该定义为True，因为单个字符也是回文的。 因此，我们可以用两个一维数组分别存储当前行和下方一行所有子串是否为回文串的情况，根据前面的分析，所有初始值都应该定义为True。 注意到最左上角的（0,0）如果递归将会超出滚动数组的范围，因此设置r的最小值为l+1，避免列举长度为1的子串即可解决问题。 在遍历过程中，只需检查当前子串是不是回文串，如果首尾不相同 or 向左下角递归的那个格子为False，这个就不是回文串，相应地把当前行的对应位置标记为False。遍历完每一行之后将当前行（now）的值赋给下方一行（former），并初始化当前行的情况。
class Solution:
def longestPalindrome(self, s: str) -> str:
le = len(s)
if le == 1:
return s
former_line = [True] * le
now_line = [True] * le
max_len = 1
longest_pali = s[0]
for l in range(le - 1, -1, -1):
for r in range(le - 1, l, -1):
if s[l] != s[r] or former_line[r - 1] == False:
now_line[r] = False
elif r - l + 1 > max_len:
max_len = r - l + 1
longest_pali = s[l:r + 1]
former_line = now_line
now_line = [True] * le
return longest_pali