1960. Maximum Product of the Length of Two Palindromic Substrings

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.

class Solution {
public:
    long long maxProduct(string s) {
        long long n = s.length(), res = 0, l = 0;
        vector<long long> p(n), r(n+1);
        queue<int> q;

        for(long long i = 0, l = 0, r = -1; i < n; i++) {
            p[i] = max(0ll, min(r-i, (l + r >= i ? p[l+r-i] : 0)));
            while(i - p[i] >= 0 and i + p[i] < n and s[i-p[i]] == s[i+p[i]])
                p[i]++;
            if(i + p[i] > r) {
                r = i + p[i];
                l = i - p[i];
            }
        }
        
        for(int i = n - 1; i >= 0; i--) {
            while(!q.empty() and q.front() - p[q.front()] + 1 > i)
                q.pop();
            r[i] = max(1 + (q.empty() ? 0ll : 2ll * (q.front() - i)), r[i+1]);
            q.push(i);
        }
        
        while(!q.empty()) q.pop();
        
        for(int i = 0; i < n; i++) {
            while(!q.empty() and q.front() + p[q.front()] <= i)
                q.pop();
            l = max(l, 1 + (q.empty() ? 0ll : 2ll * (i - q.front())));
            res = max(res, l * (r[i + 1]));
            q.push(i);
        }
        return res;
    }
};