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

发表于 更新于 分类于

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

    给你一个下标从 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：

    ```txt

    输入：s = "ababbb"

    输出：9

    解释：子字符串 "aba" 和 "bbb" 为奇数长度的回文串。乘积为 3 * 3 = 9 。

    ```

    示例 2：

    ```txt

    输入：s = "zaaaxbbby"

    输出：9

    解释：子字符串 "aaa" 和 "bbb" 为奇数长度的回文串。乘积为 3 * 3 = 9 。

    ```

    提示：

    • 2 <= s.length <= 10^5

    • s 只包含小写英文字母。

题目

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

给你一个下标从 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：

1
2
3
输入：s = "ababbb"
输出：9
解释：子字符串 "aba" 和 "bbb" 为奇数长度的回文串。乘积为 3 * 3 = 9 。

示例 2：

1
2
3
输入：s = "zaaaxbbby"
输出：9
解释：子字符串 "aaa" 和 "bbb" 为奇数长度的回文串。乘积为 3 * 3 = 9 。

提示：

  • 2 <= s.length <= 10^5
  • s 只包含小写英文字母。

题解

方法一：

思路

关键思路

找到以s[i]为中心的最长回文串长度span[i]。

接下来预处理出两个数组l和r。

l[i]代表s[0...i]内最长奇数回文串长度。

r[i]代表s[i...n-1]内最长奇数回文串长度。

枚举维护最大的l[i-1]*r[i], 1<i<n即为答案。

首先求s[i]为中心的最长回文串长度。
我们可以用字符串哈希+二分法来做，时间复杂度$O(nlogn)$，
也可以用马拉车算法，时间复杂度$O(n)$。

接下来讲述一下字符串哈希+二分的思路。

对于每个s[i]为中心的最长回文串长度如果为m，那么m-2也是以s[i]为中心的回文串。也就是说具有单调性，可以二分找出由小到大最后于一个满足的长度。时间复杂度$O(logn)$，总共有n个点所以需要$O(nlogn)$的时间复杂度。

然后一个难点就是l和r数组。

对于第s[i]可以对l[i+span[i]]做贡献，让其于i+span[i]取最大值。

同理第s[i]可以对r[i-span[i]]做贡献，让其于i-span[i]取最大值。

然后从前向后遍历取l前缀最大值，从后向前遍历取r后缀最大值。

做这里还没有结束。这里还有一个很大的坑

需要由大到小让l[i] = max(l[i], l[i+1]-2)。如果i+1是一个以l[i+1]长度结尾的回文，那么l[i]在此基础上去掉首位所以长度为l[i+1]-2

同理r[i] = max(r[i], r[i-1]-2)

代码

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
public:
    using ull = unsigned long long;
    int BASE = 131;
    long long maxProduct(string s) {
        int n = s.size();
        vector<ull> H(n+1), B(n+1, 1);
        for (int i=1; i<=n; i++) {
            H[i] = H[i-1]*BASE + s[i-1];
            B[i] = B[i-1]*BASE;
        }
        // s[i...j] = H[j]-H[i]*B[j-i]
        vector<ull> RH(n+1);
        for (int i=n-1; i>=0; i--) {
            RH[i] = RH[i+1]*BASE + s[i];
        }
        // s[i...j] = RH[i]-RH[j]*B[j-i]
        auto check = [&](int l, int r) {
            return H[r]-H[l]*B[r-l] == RH[l]-RH[r]*B[r-l];
        };
        vector<int> span(n);
        for (int i=0; i<n; i++) {
            int l = 0, r = min(i+1, n-i);
            while (l<r) {
                int m = l+r>>1;
                int x = i-m, y = i+m;
                if (check(x, y+1)) {
                    l = m+1;
                } else {
                    r = m;
                }
            }
            span[i] = r-1;
            // cout << span[i] << " ";
        }
        // cout << endl;
        vector<int> l(n), r(n);
        for (int i=0; i<n; i++) {
            l[i+span[i]] = max(l[i+span[i]], 2*span[i]+1);
        }
        for (int i=1; i<n; i++) {
            l[i] = max(l[i], l[i-1]);
        }
        for (int i=n-2; i>=0; i--) {
            l[i] = max(l[i], l[i+1]-2);
        }
        for (int i=n-1; i>=0; i--) {
            r[i-span[i]] = max(r[i-span[i]], 2*span[i]+1);
        }
        for (int i=n-2; i>=0; i--) {
            r[i] = max(r[i], r[i+1]);
        }
        for (int i=1; i<n; i++) {
            r[i] = max(r[i], r[i-1]-2);
        }
        ull ans = 0;
        for (int i=1; i<n; i++) {
            ans = max(ans, 1ull*l[i-1]*r[i]);
        }
        return ans;
    }
};

方法二：

思路

关键思路同题解一。

不同点在于求s[i]为中心的最长回文串长度。用马拉车算法，时间复杂度$O(n)$。

设$span_i$为以i为中心的回文半径。在可以让我们知道所有以i为中心的奇数长度回文串。这个回文半径不包含中心，也就是说"abcba"，'c'的回文半径是2。

$d$为遍历到当前回文串最远覆盖的下标，即$d = max(span_j+j), j \in [0, i-1]$。

设$c$为满足$d = max(span_j+j), j \in [0, i-1]$的$j$。
在求$span_i$时，$span_j,j<i$已经全部求出，对于求$span_i$：

在$i\le r$时，分两种情况：

  1. 当$span_i \le r$, 这时$span_i = span_j$, $j$是$i$关于$m$对称的点。即$span_i = span_{i-2m}$
  2. 当$span_i > r$, 对于大于$r$的部分用中心扩散法，所以可以先让$span_i = r-i$
    由这两种情况可知让$span_i = min(r-i, span_{i-2m})$, 然后再做中心扩散法。

在$i>r$时，直接使用中心扩散法。

最后便可求得$span$数组。以下标$i$为中心的回文串为[i-span[i]...span[i]+i]

代码

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
45
46
47
48
49
50
51
class Solution {
public:
    using ll = long long;
    long long maxProduct(string s) {
        int n = s.size();
        vector<int> span(n);
        int d = 0, c = 0;
        for (int i=1; i<n; i++) {
            // printf("i=%d, c=%d, d=%d\n", i, c, d);
            if (i<=d) span[i] = min(span[2*c-i], d-i);
            int l = i-span[i]-1, r = i+span[i]+1;
            while (l>=0 && r<n && s[l] == s[r]) {
                l--, r++;
                span[i]++;
            }
            if (span[i]+i > d) {
                d = span[i]+i;
                c = i;
            }
        } 
        // for (int i=0; i<n; i++) {
        //     cout << i << " " << span[i] << endl;
        // }
        vector<int> L(n), R(n);
        for (int i=0; i<n; i++) {
            // assert(i+span[i] < n);
            L[i+span[i]] = max(L[i+span[i]], 2*span[i]+1);
        }
        for (int i=1; i<n; i++) {
            L[i] = max(L[i], L[i-1]);
        }
        for (int i=n-2; i>=0; i--) {
            L[i] = max(L[i], L[i+1]-2);
        }
        for (int i=n-1; i>=0; i--) {
            // assert(i-span[i] >= 0);
            R[i-span[i]] = max(R[i-span[i]], 2*span[i]+1);
        }
        for (int i=n-2; i>=0; i--) {
            R[i] = max(R[i], R[i+1]);
        }
        for (int i=1; i<n; i++) {
            R[i] = max(R[i], R[i-1]-2);
        }
        long long ans = 0;
        for (int i=1; i<n; i++) {
            ans = max(ans, 1LL*L[i-1]*R[i]);
        }
        return ans;
    }
};