LeetCode 题解工作台
两个回文子字符串长度的最大乘积
给你一个下标从 0 开始的字符串 s ，你需要找到两个 不重叠 的回文 子字符串，它们的长度都必须为 奇数 ，使得它们长度的乘积最大。 更正式地，你想要选择四个整数 i ， j ， k ， l ，使得 0 ，且子字符串 s[i...j] 和 s[k...l] 都是回文串且长度为奇数。 s[i...j…
3
题型
4
代码语言
3
相关题
当前训练重点
困难 · string·结合·rolling·哈希
答案摘要
class Solution: def maxProduct(self, s: str) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 string·结合·rolling·哈希 题型思路
题目描述
给你一个下标从 0 开始的字符串 s ，你需要找到两个 不重叠的回文 子字符串，它们的长度都必须为 奇数 ，使得它们长度的乘积最大。
更正式地，你想要选择四个整数 i ，j ，k ，l ，使得 0 <= i <= j < k <= l < s.length ，且子字符串 s[i...j] 和 s[k...l] 都是回文串且长度为奇数。s[i...j] 表示下标从 i 到 j 且 包含 两端下标的子字符串。
请你返回两个不重叠回文子字符串长度的 最大 乘积。
回文字符串 指的是一个从前往后读和从后往前读一模一样的字符串。子字符串 指的是一个字符串中一段连续字符。
示例 1：
输入：s = "ababbb" 输出：9 解释：子字符串 "aba" 和 "bbb" 为奇数长度的回文串。乘积为 3 * 3 = 9 。
示例 2：
输入：s = "zaaaxbbby" 输出：9 解释：子字符串 "aaa" 和 "bbb" 为奇数长度的回文串。乘积为 3 * 3 = 9 。
提示：
2 <= s.length <= 105s只包含小写英文字母。
解题思路
方法一
class Solution:
def maxProduct(self, s: str) -> int:
n = len(s)
hlen = [0] * n
center = right = 0
for i in range(n):
if i < right:
hlen[i] = min(right - i, hlen[2 * center - i])
while (
0 <= i - 1 - hlen[i]
and i + 1 + hlen[i] < len(s)
and s[i - 1 - hlen[i]] == s[i + 1 + hlen[i]]
):
hlen[i] += 1
if right < i + hlen[i]:
center, right = i, i + hlen[i]
prefix = [0] * n
suffix = [0] * n
for i in range(n):
prefix[i + hlen[i]] = max(prefix[i + hlen[i]], 2 * hlen[i] + 1)
suffix[i - hlen[i]] = max(suffix[i - hlen[i]], 2 * hlen[i] + 1)
for i in range(1, n):
prefix[~i] = max(prefix[~i], prefix[~i + 1] - 2)
suffix[i] = max(suffix[i], suffix[i - 1] - 2)
for i in range(1, n):
prefix[i] = max(prefix[i - 1], prefix[i])
suffix[~i] = max(suffix[~i], suffix[~i + 1])
return max(prefix[i - 1] * suffix[i] for i in range(1, n))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) using Manacher's algorithm to generate palindromes and O(n) to combine prefix and suffix maximums. Space complexity is O(n) for storing radii and prefix/suffix arrays. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if candidate palindromes overlap before computing the product.
- question_mark
Consider using rolling hash for substring verification if needed.
- question_mark
Observe that only odd-length palindromes are relevant; even lengths are ignored.
常见陷阱
外企场景- error
Counting even-length palindromes mistakenly, which violates the problem constraint.
- error
Overlapping substrings causing invalid product calculations.
- error
Using nested loops to compare all palindrome pairs, which is too slow for large strings.
进阶变体
外企场景- arrow_right_alt
Maximize the sum of lengths instead of the product of two non-overlapping odd-length palindromes.
- arrow_right_alt
Consider even-length palindromes alongside odd-length palindromes for maximum product.
- arrow_right_alt
Restrict palindromes to a minimum length k, requiring adjusted prefix/suffix calculations.