Skip to content

Latest commit

 

History

History
115 lines (98 loc) · 4.95 KB

README.md

File metadata and controls

115 lines (98 loc) · 4.95 KB

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 <= 105
  • s consists of lowercase English letters.

Companies:
Codenation

Related Topics:
String, Rolling Hash, Hash Function

Solution 1. Manacher

// OJ: https://leetcode.com/problems/maximum-product-of-the-length-of-two-palindromic-substrings/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
// Ref: https://leetcode.com/problems/maximum-product-of-the-length-of-two-palindromic-substrings/discuss/1389958/Manacher-and-Queue
class Solution {
public:
    long long maxProduct(string s) {
        int N = s.size(), j = 0;
        vector<int> r(N, 1);
        for (int i = 1; i < N; ++i) {
            int cur = j + r[j] > i ? min(r[2 * j - i], j + r[j] - i) : 1;
            while (i - cur >= 0 && i + cur < N && s[i - cur] == s[i + cur]) ++cur;
            if (i + cur > j + r[j]) j = i;
            r[i] = cur;
        }
        vector<int> right(N, 1); // right[i] is the length of the longest palinedome in [i, n)
        queue<array<int, 2>> q, q1; // index, range
        for (int i = N - 1; i >= 0; --i) {
            while (q.size() && q.front()[0] - q.front()[1] >= i) q.pop(); // if the queue front's range can't cover `i`, pop it.
            q.push({i, r[i]});
            right[i] = 1 + (q.front()[0] - i) * 2; // now queue front is the rightmost range that can cover `i`. It must be the center of the longest palindrom in `[i, n)`.
        }
        int left = 0; // left is the length of the longest palindrome in [0, i]. 
        long long ans = 1;
        for (int i = 0; i < N - 1; ++i) {
            while (q1.size() && q1.front()[0] + q1.front()[1] <= i) q1.pop();
            q1.push({i, r[i]});
            left = max(left, 1 + (i - q1.front()[0]) * 2);
            ans = max(ans, (long long)left * right[i + 1]);
        }
        return ans;
    }
};

Or

// OJ: https://leetcode.com/problems/maximum-product-of-the-length-of-two-palindromic-substrings/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
// Ref: https://leetcode.com/problems/maximum-product-of-the-length-of-two-palindromic-substrings/discuss/1389958/Manacher-and-Queue
class Solution {
    vector<int> manacher(string s, int N) {
        vector<int> r(N, 1), mx(N, 1);
        int j = 0;
        for (int i = 1; i < N; ++i) {
            int cur = j + r[j] > i ? min(r[2 * j - i], j + r[j] - i) : 1;
            while (i - cur >= 0 && i + cur < N && s[i + cur] == s[i - cur]) {
                mx[i + cur] = 2 * cur + 1; // now `mx[i]` is the length of the longest palindrome ending at `s[i]`.
                ++cur;
            }
            if (i + cur > j + r[j]) j = i;
            r[i] = cur;
        }
        for (int i = 1; i < N; ++i) mx[i] = max(mx[i], mx[i - 1]); // now `mx[i]` is the length of the longest palindrome in `s[0..i]`.
        return mx;
    }
public:
    long long maxProduct(string s) {
        long long ans = 1, N = s.size();
        auto l2r = manacher(s, N);
        auto r2l = manacher(string(rbegin(s), rend(s)), N);
        for (int i = 0, j = N - 2; i < N - 1; ++i, --j) {
            ans = max(ans, (long long)l2r[i] * r2l[j]);
        }
        return ans;
    }
};