原文链接: https://leetcode-cn.com/problems/maximum-product-of-the-length-of-two-palindromic-substrings
英文原文
You are given a 0-indexed string s and are tasked with finding two non-intersecting palindromic substrings of odd length such that the product of their lengths is maximized.
More formally, you want to choose four integers i, j, k, l such that 0 <= i <= j < k <= l < s.length and both the substrings s[i...j] and s[k...l] are palindromes and have odd lengths. s[i...j] denotes a substring from index i to index j inclusive.
Return the maximum possible product of the lengths of the two non-intersecting palindromic substrings.
A palindrome is a string that is the same forward and backward. A substring is a contiguous sequence of characters in a string.
Example 1:
Input: s = "ababbb" Output: 9 Explanation: Substrings "aba" and "bbb" are palindromes with odd length. product = 3 * 3 = 9.
Example 2:
Input: s = "zaaaxbbby" Output: 9 Explanation: Substrings "aaa" and "bbb" are palindromes with odd length. product = 3 * 3 = 9.
Constraints:
2 <= s.length <= 105sconsists of lowercase English letters.
中文题目
给你一个下标从 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只包含小写英文字母。
通过代码
高赞题解
方法一：$\text{manacher}$ 算法 + 扫描线
前言
本题严重超纲，笔试不太可能考，面试一定不会考（如果在简历里没写是 icpc 选手的前提下考了，请发邮件给 hr 举报没有 b 数的面试官）。题解仅供感兴趣的读者学习使用。
其实做这道题之前我也不会 $\text{manacher}$ 算法，是去现学的（手动捂脸
第一步
第一步当然是要把以每个位置为中心的最长回文串长度求出来。
比较快的 $O(n)$ 做法是使用 $\text{manacher}$ 算法，比较慢 $O(n \log n)$ 而且常数较大再而且不是 $100%$ 正确的做法是使用字符串哈希。字符串哈希我在这里不打算详细说了，大概就是「枚举中间位置 $O(n)$ + 二分查找回文串长度 $O(\log n)$ + 字符串哈希判断左右半边是否相同 $O(1)$」。$\text{manacher}$ 算法的话官方题解里面也出现过：
- 「5. 最长回文子串」的官方题解的方法三
除此之外我比较推荐 oi-wiki 上讲 $\text{manacher}$ 算法的文章，非常详细，我一遍就看懂了。
然后现在假设读者知道 $\text{manacher}$ 算法怎么写了。由于本题只需要找奇数长度的回文串，所以在使用 $\text{manacher}$ 算法之前，就不需要在字符之间插一个无效字符了。
第二步
现在假设读者已经求出了字符串 $s$ 的每个位置为中心的最长回文串长度 $\textit{span}[i]$，这里 $\textit{span}[i]$ 表示有一个长度为 $2 \cdot \textit{span}[i] - 1$ 的回文串，那么怎么挑两个最长且不重叠的呢？
可以想到使用前缀和后缀和的方法。假设 $\textit{pre}[i]$ 表示 $s[0..i]$ 中最长回文串的长度，$\textit{suf}[i]$ 表示 $s[i..n-1]$ 中最长回文串的长度，这样我们枚举 $i$ 作为两个回文串的分界位置，$\textit{pre}[i] \cdot \textit{suf}[i+1]$ 中的最大值即为答案。
现在的问题就是求 $\textit{pre}[i]$ 和 $\textit{suf}[i]$ 了。由于这两个玩意是很类似的，因此我们就讲讲 $\textit{pre}[i]$ 怎么求。要是看了 $\textit{pre}[i]$ 还不会求 $\textit{suf}[i]$ 的话，大不了把字符串翻转一下再调用求 $\textit{pre}[i]$ 的代码。
第三步
有些读者可能会想出一个这样的方法：
首先我们枚举 $i$，由于以 $s[i]$ 为中心的最长回文串是 $s\big[i-\textit{span}[i]+1, i+\textit{span}[i]-1\big]$，那么我们将 $\textit{pre}[i+\textit{span}-1]$ 更新为其与 $2 \cdot \textit{span}[i] - 1$ 的较大值；
然后我们再枚举 $i$，将 $\textit{pre}[i]$ 更新为其与 $\textit{pre}[i-1]$ 的较大值。
直观上来说，这种方法就是将最长回文串的长度挂载在右边界上，然后求一下前缀和得到 $\textit{pre}[i]$，可惜这种方法只对了一半。最简单的反例就是，如果 $s$ 整体就是一个类似于 $\texttt{zyxw…cbabc…wxyz}$ 的回文串，那么这样遍历完只有 $\textit{pre}[n-1]$ 有值，其余 $\textit{pre}[..]$ 均为 $1$，这样显然是不正确的。
那么应该如何解决这个问题呢？我们只需要再反着遍历一遍 $i$，将 $\textit{pre}[i]$ 更新为其与 $\textit{pre}[i+1] - 2$ 的较大值即可。其妙处就在于：
如果以位置 $i+1$ 为右边界，有一个长度为 $\textit{pre}[i+1]$ 的回文串，那么以位置 $i$ 为右边界，就有一个长度为 $\textit{pre}[i+1]-2$ 的回文串，也就是将前者的首尾两个字符去掉。
这种方法的本质模型为：
我们有一个数组 $\textit{pre}$，初始时每个元素均为 $0$；
我们需要进行 $n$ 次更新操作，每一次更新给定一个右边界 $r$ 以及价值 $v$，将所有下标大于等于 $r$ 的元素更新为其与 $v$ 的较大值，将所有下标小于 $r$ 的元素（假设下标为 $i$）更新为其与 $v - 2(r-i)$ 的较大值；
最终返回更新完成后的结果。
第四步
写代码！
代码
[sol1-C++]class Solution { public: long long maxProduct(string s) { int n = s.size(); vector<int> span(n); // manacher for (int i = 0, l = 0, r = -1; i < n; ++i) { span[i] = (i <= r ? min(span[l + r - i], r - i + 1) : 1); while (i - span[i] >= 0 && i + span[i] < n && s[i - span[i]] == s[i + span[i]]) { ++span[i]; } if (i + span[i] - 1 > r) { l = i - span[i] + 1; r = i + span[i] - 1; } } vector<int> pre(n), suf(n); for (int i = 0; i < n; ++i) { pre[i + span[i] - 1] = max(pre[i + span[i] - 1], span[i] * 2 - 1); suf[i - span[i] + 1] = max(suf[i - span[i] + 1], span[i] * 2 - 1); } for (int i = 1; i < n; ++i) { pre[i] = max(pre[i], pre[i - 1]); } for (int i = n - 2; i >= 0; --i) { pre[i] = max(pre[i], pre[i + 1] - 2); } for (int i = n - 2; i >= 0; --i) { suf[i] = max(suf[i], suf[i + 1]); } for (int i = 1; i < n; ++i) { suf[i] = max(suf[i], suf[i - 1] - 2); } long long ans = 0; for (int i = 0; i < n - 1; ++i) { ans = max(ans, (long long)pre[i] * suf[i + 1]); } return ans; } };
[sol1-Python3]class Solution: def maxProduct(self, s: str) -> int: n = len(s) span = [0] * n l, r = 0, -1 for i in range(n): span[i] = (min(span[l + r - i], r - i + 1) if i <= r else 1) while i - span[i] >= 0 and i + span[i] < n and s[i - span[i]] == s[i + span[i]]: span[i] += 1 if i + span[i] - 1 > r: l = i - span[i] + 1 r = i + span[i] - 1 pre, suf = [0] * n, [0] * n for i in range(n): pre[i + span[i] - 1] = max(pre[i + span[i] - 1], span[i] * 2 - 1) suf[i - span[i] + 1] = max(suf[i - span[i] + 1], span[i] * 2 - 1) for i in range(1, n): pre[i] = max(pre[i], pre[i - 1]) for i in range(n - 2, -1, -1): pre[i] = max(pre[i], pre[i + 1] - 2) for i in range(n - 2, -1, -1): suf[i] = max(suf[i], suf[i + 1]) for i in range(1, n): suf[i] = max(suf[i], suf[i - 1] - 2) ans = max(pre[i] * suf[i + 1] for i in range(n - 1)) return ans
离谱
这里 有一道非常类似的题目。
虽然现在 $\text{manacher}$ 算法在竞赛圈里已经挺普及的了，但在 2012 年，这是个国家集训队难度的考点。
所以说如果程序员找工作，笔试面试考 $\text{manacher}$ 算法的话，是真的离谱。如果学有余力或者对算法竞赛感兴趣的话，倒可以学一学，尤其是仔细领悟一下 $\text{manacher}$ 算法时间复杂度证明的部分。
复杂度分析
时间复杂度：$O(n)$。
空间复杂度：$O(n)$。
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 684 | 2398 | 28.5% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
