1960-两个回文子字符串长度的最大乘积

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

给你一个下标从 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 <= 105
  • s 只包含小写英文字母。

方法一：manacher 算法 + 扫描线

前言

本题严重超纲，笔试不太可能考，面试一定不会考（如果在简历里没写是 icpc 选手的前提下考了，请发邮件给 hr 举报没有 b 数的面试官）。题解仅供感兴趣的读者学习使用。

其实做这道题之前我也不会 manacher 算法，是去现学的（手动捂脸

第一步

第一步当然是要把以每个位置为中心的最长回文串长度求出来。

比较快的 O(n) 做法是使用 manacher 算法，比较慢 O(n \log n) 而且常数较大再而且不是 100% 正确的做法是使用字符串哈希。字符串哈希我在这里不打算详细说了，大概就是「枚举中间位置 O(n) + 二分查找回文串长度 O(\log n) + 字符串哈希判断左右半边是否相同 O(1)」。manacher 算法的话官方题解里面也出现过：

然后现在假设读者知道 manacher 算法怎么写了。由于本题只需要找奇数长度的回文串，所以在使用 manacher 算法之前，就不需要在字符之间插一个无效字符了。

第二步

现在假设读者已经求出了字符串 s 的每个位置为中心的最长回文串长度 span}[i]，这里 span}[i] 表示有一个长度为 2 \cdot \textit{span}[i] - 1 的回文串，那么怎么挑两个最长且不重叠的呢？

可以想到使用前缀和后缀和的方法。假设 pre}[i] 表示 s[0..i] 中最长回文串的长度，suf}[i] 表示 s[i..n-1] 中最长回文串的长度，这样我们枚举 i 作为两个回文串的分界位置，pre}[i] \cdot \textit{suf}[i+1] 中的最大值即为答案。

现在的问题就是求 pre}[i] 和 suf}[i] 了。由于这两个玩意是很类似的，因此我们就讲讲 pre}[i] 怎么求。要是看了 pre}[i] 还不会求 suf}[i] 的话，大不了把字符串翻转一下再调用求 pre}[i] 的代码。

第三步

有些读者可能会想出一个这样的方法：

  • 首先我们枚举 i，由于以 s[i] 为中心的最长回文串是 s\big[i-\textit{span}[i]+1, i+\textit{span}[i]-1\big]，那么我们将 pre}[i+\textit{span}-1] 更新为其与 2 \cdot \textit{span}[i] - 1 的较大值；

  • 然后我们再枚举 i，将 pre}[i] 更新为其与 pre}[i-1] 的较大值。

直观上来说，这种方法就是将最长回文串的长度挂载在右边界上，然后求一下前缀和得到 pre}[i]，可惜这种方法只对了一半。最简单的反例就是，如果 s 整体就是一个类似于 zyxw…cbabc…wxyz 的回文串，那么这样遍历完只有 pre}[n-1] 有值，其余 pre}[..] 均为 1，这样显然是不正确的。

那么应该如何解决这个问题呢？我们只需要再反着遍历一遍 i，将 pre}[i] 更新为其与 pre}[i+1] - 2 的较大值即可。其妙处就在于：

如果以位置 i+1 为右边界，有一个长度为 pre}[i+1] 的回文串，那么以位置 i 为右边界，就有一个长度为 pre}[i+1]-2 的回文串，也就是将前者的首尾两个字符去掉。

这种方法的本质模型为：

  • 我们有一个数组 pre，初始时每个元素均为 0；

  • 我们需要进行 n 次更新操作，每一次更新给定一个右边界 r 以及价值 v，将所有下标大于等于 r 的元素更新为其与 v 的较大值，将所有下标小于 r 的元素（假设下标为 i）更新为其与 v - 2(r-i) 的较大值；

  • 最终返回更新完成后的结果。

第四步

写代码！

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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

复杂度分析

  • 时间复杂度：O(n)。

  • 空间复杂度：O(n)。

 Comments
On this page
1960-两个回文子字符串长度的最大乘积