Maximum Product of the Length of Two Palindromic Substrings LeetCode solution in C++

1
class Solution {
2
 public:
3
  long long maxProduct(string s) {
4
    int n = s.size();
5
    vector<int> d1 = vector<int>(s.size(), 0);
6
    for (int i = 0, l = 0, r = -1; i < n; i++) {
7
      int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
8
      while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
9
        k++;
10
      }
11
      d1[i] = k--;
12
      if (i + k > r) {
13
        l = i - k;
14
        r = i + k;
15
      }
16
    }
17

18
    vector<int> maxL = vector<int>(s.size(), 1);
19
    auto lQueue = set<pair<int, int>>();
20
    for (int i = 0; i < s.size(); i++) {
21
      if (i > 0) maxL[i] = max(maxL[i], maxL[i - 1]);
22

23
      lQueue.insert({i, d1[i]});
24

25
      while (lQueue.begin()->first + lQueue.begin()->second - 1 < i) {
26
        lQueue.erase(lQueue.begin());
27
      }
28

29
      maxL[i] = max(maxL[i], ((i - lQueue.begin()->first) * 2) + 1);
30
    }
31

32
    vector<int> maxR = vector<int>(s.size(), 1);
33
    auto rQueue = priority_queue<pair<int, int>>();
34

35
    for (int i = s.size() - 1; i >= 0; i--) {
36
      if (i < s.size() - 1) maxR[i] = max(maxR[i], maxR[i + 1]);
37

38
      rQueue.push({i, d1[i]});
39

40
      while (rQueue.top().first - (rQueue.top().second - 1) > i) {
41
        rQueue.pop();
42
      }
43

44
      maxR[i] = max(maxR[i], ((rQueue.top().first - i) * 2) + 1);
45
    }
46

47
    long long res = 0;
48
    for (int i = 0; i < s.size() - 1; i++) {
49
      res = max(res, (long long)maxL[i] * (long long)maxR[i + 1]);
50
    }
51
    return res;
52
  }
53
};