Hard

题目描述

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

解题思路

这道题要求找到两个不相交的奇数长度回文子字符串，使其长度乘积最大。

核心思路：

  1. 使用 Manacher 算法 找出以每个位置为中心的最长奇数回文串长度
  2. 对于每个分割点 i，计算左半部分 [0...i] 和右半部分 [i+1...n-1] 中的最长奇数回文串
  3. 枚举所有分割点，计算乘积的最大值

详细步骤：

  • Manacher 算法预处理出每个中心位置的最长回文半径
  • 从左到右扫描，维护 prefix[i] 表示前缀 s[0...i] 中最长奇数回文串长度
  • 从右到左扫描，维护 suffix[i] 表示后缀 s[i...n-1] 中最长奇数回文串长度
  • 枚举分割点 i，答案为 max(prefix[i] * suffix[i+1])

优化要点：

  • Manacher 算法在 O(n) 时间内解决回文串问题
  • 预处理前缀和后缀的最长回文串，避免重复计算
  • 只考虑奇数长度回文串，简化处理逻辑

代码实现

class Solution {
public:
    long long maxProduct(string s) {
        int n = s.length();
        vector<int> radius = manacher(s);
        
        // prefix[i] = 前缀s[0...i]中最长奇数回文串长度
        vector<int> prefix(n, 1);
        for (int i = 0; i < n; i++) {
            int len = 2 * radius[i] + 1;
            int left = i - radius[i];
            int right = i + radius[i];
            for (int j = left; j <= right; j++) {
                if (j >= 0 && j < n) {
                    int palindromeLen = 2 * (min(j - left, right - j)) + 1;
                    prefix[j] = max(prefix[j], palindromeLen);
                }
            }
        }
        
        // 更新prefix数组，确保单调性
        for (int i = 1; i < n; i++) {
            prefix[i] = max(prefix[i], prefix[i-1]);
        }
        
        // suffix[i] = 后缀s[i...n-1]中最长奇数回文串长度
        vector<int> suffix(n, 1);
        for (int i = 0; i < n; i++) {
            int len = 2 * radius[i] + 1;
            int left = i - radius[i];
            int right = i + radius[i];
            for (int j = left; j <= right; j++) {
                if (j >= 0 && j < n) {
                    int palindromeLen = 2 * (min(j - left, right - j)) + 1;
                    suffix[j] = max(suffix[j], palindromeLen);
                }
            }
        }
        
        // 更新suffix数组，确保单调性
        for (int i = n - 2; i >= 0; i--) {
            suffix[i] = max(suffix[i], suffix[i+1]);
        }
        
        long long result = 1;
        for (int i = 0; i < n - 1; i++) {
            result = max(result, (long long)prefix[i] * suffix[i+1]);
        }
        
        return result;
    }
    
private:
    vector<int> manacher(string s) {
        int n = s.length();
        vector<int> radius(n, 0);
        int center = 0, right = 0;
        
        for (int i = 0; i < n; i++) {
            if (i < right) {
                radius[i] = min(radius[2 * center - i], right - i);
            }
            
            while (i - radius[i] - 1 >= 0 && i + radius[i] + 1 < n && 
                   s[i - radius[i] - 1] == s[i + radius[i] + 1]) {
                radius[i]++;
            }
            
            if (i + radius[i] > right) {
                center = i;
                right = i + radius[i];
            }
        }
        
        return radius;
    }
};

class Solution:
    def maxProduct(self, s: str) -> int:
        n = len(s)
        radius = self.manacher(s)
        
        # prefix[i] = 前缀s[0:i+1]中最长奇数回文串长度
        prefix = [1] * n
        for i in range(n):
            length = 2 * radius[i] + 1
            left = i - radius[i]
            right = i + radius[i]
            for j in range(left, right + 1):
                if 0 <= j < n:
                    palindrome_len = 2 * min(j - left, right - j) + 1
                    prefix[j] = max(prefix[j], palindrome_len)
        
        # 更新prefix数组，确保单调性
        for i in range(1, n):
            prefix[i] = max(prefix[i], prefix[i-1])
        
        # suffix[i] = 后缀s[i:]中最长奇数回文串长度
        suffix = [1] * n
        for i in range(n):
            length = 2 * radius[i] + 1
            left = i - radius[i]
            right = i + radius[i]
            for j in range(left, right + 1):
                if 0 <= j < n:
                    palindrome_len = 2 * min(j - left, right - j) + 1
                    suffix[j] = max(suffix[j], palindrome_len)
        
        # 更新suffix数组，确保单调性
        for i in range(n - 2, -1, -1):
            suffix[i] = max(suffix[i], suffix[i+1])
        
        result = 1
        for i in range(n - 1):
            result = max(result, prefix[i] * suffix[i+1])
        
        return result
    
    def manacher(self, s: str) -> list:
        n = len(s)
        radius = [0] * n
        center = right = 0
        
        for i in range(n):
            if i < right:
                radius[i] = min(radius[2 * center - i], right - i)
            
            while (i - radius[i] - 1 >= 0 and i + radius[i] + 1 < n and 
                   s[i - radius[i] - 1] == s[i + radius[i] + 1]):
                radius[i] += 1
            
            if i + radius[i] > right:
                center = i
                right = i + radius[i]
        
        return radius

public class Solution {
    public long MaxProduct(string s) {
        int n = s.Length;
        int[] radius = Manacher(s);
        
        // prefix[i] = 前缀s[0...i]中最长奇数回文串长度
        int[] prefix = new int[n];
        for (int i = 0; i < n; i++) prefix[i] = 1;
        
        for (int i = 0; i < n; i++) {
            int length = 2 * radius[i] + 1;
            int left = i - radius[i];
            int right = i + radius[i];
            for (int j = left; j <= right; j++) {
                if (j >= 0 && j < n) {
                    int palindromeLen = 2 * Math.Min(j - left, right - j) + 1;
                    prefix[j] = Math.Max(prefix[j], palindromeLen);
                }
            }
        }
        
        // 更新prefix数组，确保单调性
        for (int i = 1; i < n; i++) {
            prefix[i] = Math.Max(prefix[i], prefix[i-1]);
        }
        
        // suffix[i] = 后缀s[i...n-1]中最长奇数回文串长度
        int[] suffix = new int[n];
        for (int i = 0; i < n; i++) suffix[i] = 1;
        
        for (int i = 0; i < n; i++) {
            int length = 2 * radius[i] + 1;
            int left = i - radius[i];
            int right = i + radius[i];
            for (int j = left; j <= right; j++) {
                if (j >= 0 && j < n) {
                    int palindromeLen = 2 * Math.Min(j - left, right - j) + 1;
                    suffix[j] = Math.Max(suffix[j], palindromeLen);
                }
            }
        }
        
        // 更新suffix数组，确保单调性
        for (int i = n - 2; i >= 0; i--) {
            suffix[i] = Math.Max(suffix[i], suffix[i+1]);
        }
        
        long result = 1;
        for (int i = 0; i < n - 1; i++) {
            result = Math.Max(result, (long)prefix[i] * suffix[i+1]);
        }
        
        return result;
    }
    
    private int[] Manacher(string s) {
        int n = s.Length;
        int[] radius = new int[n];
        int center = 0, right = 0;
        
        for (int i = 0; i < n; i++) {
            if (i < right) {
                radius[i] = Math.Min(radius[2 * center - i], right - i);
            }
            
            while (i - radius[i] - 1 >= 0 && i + radius[i] + 1 < n && 
                   s[i - radius[i] - 1] == s[i + radius[i] + 1]) {
                radius[i]++;
            }
            
            if (i + radius[i] > right) {
                center = i;
                right = i + radius[i];
            }
        }
        
        return radius;
    }
}

var maxProduct = function(s) {
    const n = s.length;
    const radius = manacher(s);
    
    // prefix[i] = 前缀s[0...i]中最长奇数回文串长度
    const prefix = new Array(n).fill(1);
    for (let i = 0; i < n; i++) {
        const length = 2 * radius[i] + 1;
        const left = i - radius[i];
        const right = i + radius[i];
        for (let j = left; j <= right; j++) {
            if (j >= 0 && j < n) {
                const palindromeLen = 2 * Math.min(j - left, right - j) + 1;
                prefix[j] = Math.max(prefix[j], palindromeLen);
            }
        }
    }
    
    // 更新prefix数组，确保单调性
    for (let i = 1; i < n; i++) {
        prefix[i] = Math.max(prefix[i], prefix[i-1]);
    }
    
    // suffix[i] = 后缀s[i...n-1]中最长奇数回文串长度
    const suffix = new Array(n).fill(1);
    for (let i = 0; i < n; i++) {
        const length = 2 * radius[i] + 1;
        const left = i - radius[i];
        const right = i + radius[i];
        for (let j = left; j <= right; j++) {
            if (j >= 0 && j < n) {
                const palindromeLen = 2 * Math.min(j - left, right - j) + 1;
                suffix[j] = Math.max(suffix[j], palindromeLen);
            }
        }
    }
    
    // 更新suffix数组，确保单调性
    for (let i = n - 2; i >= 0; i--) {
        suffix[i] = Math.max(suffix[i], suffix[i+1]);
    }
    
    let result = 1;
    for (let i = 0; i < n - 1; i++) {
        result = Math.max(result, prefix[i] * suffix[i+1]);
    }
    
    return result;
};

function manacher(s) {
    const n = s.length;
    const radius = new Array(n).fill(0);
    let center = 0, right = 0;
    
    for (let i = 0; i < n; i++) {
        if (i < right) {
            radius[i] = Math.min(radius[2 * center - i], right - i);
        }
        
        while (i - radius[i] - 1 >= 0 && i + radius[i] + 1 < n && 
               s[i - radius[i] - 1]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度
时间-
空间-

相关题目