Maximum Product of the Length of Two Palindromic Substrings LeetCode solution in Java

1
// using manachers algorithm
2

3
class Solution {
4

5
  public long maxProduct(String s) {
6
    int n = s.length();
7
    if (n == 2) return 1;
8
    int[] len = manachers(s); // get lengths of palindromes at each element
9

10
    long left[] = new long[n]; // stores the max length of palindrome to left of each index
11

12
    int max = 1;
13
    left[0] = max;
14
    for (int i = 1; i <= n - 1; i++) {
15
      // does any palindrome end at i with length greater than max
16
      if (len[(i - max - 1 + i) / 2] > max) max += 2;
17
      left[i] = max;
18
    }
19
    max = 1;
20
    long[] right = new long[n]; // stores the max length of palindrome to right of each index
21
    right[n - 1] = max;
22

23
    for (int i = n - 2; i >= 0; i--) {
24
      // does any palindrome start at i with length greater than max
25
      if (len[(i + max + 1 + i) / 2] > max) max += 2;
26
      right[i] = max;
27
    }
28

29
    long res = 1;
30

31
    for (int i = 1; i < n; i++) {
32
      res = Math.max(res, left[i - 1] * right[i]);
33
    }
34
    return res;
35
  }
36

37
  // credit :
38
  // https://hackernoon.com/manachers-algorithm-explained-longest-palindromic-substring-22cb27a5e96f
39
  private int[] manachers(String s) {
40

41
    int len = s.length();
42
    int[] P = new int[len];
43
    int c = 0; // stores the center of the longest palindromic substring until now
44
    int r = 0; // stores the right boundary of the longest palindromic substring until now
45
    int maxLen = 0;
46

47
    for (int i = 0; i < len; i++) {
48
      // get mirror index of i
49
      int mirror = (2 * c) - i;
50

51
      // see if the mirror of i is expanding beyond the left boundary of current longest palindrome
52
      // at center c
53
      // if it is, then take r - i as P[i]
54
      // else take P[mirror] as P[i]
55
      if (i < r) {
56
        P[i] = Math.min(r - i, P[mirror]);
57
      }
58

59
      // expand at i
60
      int a = i + (1 + P[i]);
61
      int b = i - (1 + P[i]);
62
      while (a < len && b >= 0 && s.charAt(a) == s.charAt(b)) {
63
        P[i]++;
64
        a++;
65
        b--;
66
      }
67

68
      // check if the expanded palindrome at i is expanding beyond the right boundary of current
69
      // longest palindrome at center c
70
      // if it is, the new center is i
71
      if (i + P[i] > r) {
72
        c = i;
73
        r = i + P[i];
74
      }
75
    }
76
    for (int i = 0; i < len; i++) P[i] = 1 + 2 * P[i];
77
    return P;
78
  }
79
}