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

Difficulty: 困难

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

Solution

Language: ****

 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

class Solution {
public:
    long long maxProduct(string s) {
        int n = s.size();
        vector<int> span(n);
        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;

    }
};