Skip to content

1960. Maximum Product of the Length of Two Palindromic Substrings 👍

Approach 1: Manacher

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
 public:
  long long maxProduct(string s) {
    const int n = s.length();
    long long ans = 1;
    // l[i] := max length of palindromes in s[0..i)
    vector<int> l = manacher(s, n);
    // r[i] := max length of palindromes in s[i..n)
    vector<int> r = manacher(string(s.rbegin(), s.rend()), n);
    reverse(r.begin(), r.end());

    for (int i = 0; i + 1 < n; ++i)
      ans = max(ans, (long long)l[i] * r[i + 1]);

    return ans;
  }

 private:
  vector<int> manacher(const string& s, int n) {
    vector<int> maxExtends(n);
    vector<int> l2r(n, 1);
    int center = 0;

    for (int i = 0; i < n; ++i) {
      const int r = center + maxExtends[center] - 1;
      const int mirrorIndex = center - (i - center);
      int extend = i > r ? 1 : min(maxExtends[mirrorIndex], r - i + 1);
      while (i - extend >= 0 && i + extend < n &&
             s[i - extend] == s[i + extend]) {
        l2r[i + extend] = 2 * extend + 1;
        ++extend;
      }
      maxExtends[i] = extend;
      if (i + maxExtends[i] >= r)
        center = i;
    }

    for (int i = 1; i < n; ++i)
      l2r[i] = max(l2r[i], l2r[i - 1]);

    return l2r;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
  public long maxProduct(String s) {
    final int n = s.length();
    long ans = 1;
    // l[i] := max length of palindromes in s[0..i)
    int[] l = manacher(s, n);
    // r[i] := max length of palindromes in s[i..n)
    int[] r = manacher(new StringBuilder(s).reverse().toString(), n);

    reverse(r, 0, n - 1);

    for (int i = 0; i + 1 < n; ++i)
      ans = Math.max(ans, (long) l[i] * r[i + 1]);

    return ans;
  }

  private int[] manacher(final String s, int n) {
    int[] maxExtends = new int[n];
    int[] l2r = new int[n];
    Arrays.fill(l2r, 1);
    int center = 0;

    for (int i = 0; i < n; ++i) {
      final int r = center + maxExtends[center] - 1;
      final int mirrorIndex = center - (i - center);
      int extend = i > r ? 1 : Math.min(maxExtends[mirrorIndex], r - i + 1);
      while (i - extend >= 0 && i + extend < n && s.charAt(i - extend) == s.charAt(i + extend)) {
        l2r[i + extend] = 2 * extend + 1;
        ++extend;
      }
      maxExtends[i] = extend;
      if (i + maxExtends[i] >= r)
        center = i;
    }

    for (int i = 1; i < n; ++i)
      l2r[i] = Math.max(l2r[i], l2r[i - 1]);

    return l2r;
  }

  private void reverse(int[] A, int l, int r) {
    while (l < r)
      swap(A, l++, r--);
  }

  private void swap(int[] A, int i, int j) {
    final int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
  def maxProduct(self, s: str) -> int:
    n = len(s)

    def manacher(s: str) -> List[int]:
      maxExtends = [0] * n
      l2r = [1] * n
      center = 0

      for i in range(n):
        r = center + maxExtends[center] - 1
        mirrorIndex = center - (i - center)
        extend = 1 if i > r else min(maxExtends[mirrorIndex], r - i + 1)
        while i - extend >= 0 and i + extend < n and s[i - extend] == s[i + extend]:
          l2r[i + extend] = 2 * extend + 1
          extend += 1
        maxExtends[i] = extend
        if i + maxExtends[i] >= r:
          center = i

      for i in range(1, n):
        l2r[i] = max(l2r[i], l2r[i - 1])

      return l2r

    # l[i] := max length of palindromes in s[0..i)
    l = manacher(s)
    # r[i] := max length of palindromes in s[i..n)
    r = manacher(s[::-1])[::-1]
    return max(l[i] * r[i + 1] for i in range(n - 1))

Approach 2: Rolling Hash

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class Solution {
 public:
  long long maxProduct(string s) {
    const int n = s.length();
    long long ans = 1;
    vector<long> pow(n + 1);        // pow[i] := kBase^i
    vector<long> hashFromL(n + 1);  // hashFromL[i] = hash of s[0..i)
    vector<long> hashFromR(n + 1);  // hashFromR[i] = hash of s[i..n)
    vector<int> l(n);  // l[i] := max length of palindromes in s[0..i)
    vector<int> r(n);  // r[i] := max length of palindromes in s[i..n)

    pow[0] = 1;
    for (int i = 1; i <= n; ++i)
      pow[i] = pow[i - 1] * kBase % kMod;

    for (int i = 1; i <= n; ++i)
      hashFromL[i] = (hashFromL[i - 1] * kBase + val(s[i - 1])) % kMod;

    for (int i = n - 1; i >= 0; --i)
      hashFromR[i] = (hashFromR[i + 1] * kBase + val(s[i])) % kMod;

    int max = 1;  // max length of palindromes so far
    for (int i = 0; i < n; i++) {
      if (i - max - 1 >= 0 &&
          isPalindrome(i - max - 1, i + 1, hashFromL, hashFromR, pow))
        max += 2;
      l[i] = max;
    }

    // Fill in r.
    max = 1;
    for (int i = n - 1; i >= 0; i--) {
      if (i + max + 2 <= n &&
          isPalindrome(i, i + max + 2, hashFromL, hashFromR, pow))
        max += 2;
      r[i] = max;
    }

    for (int i = 0; i + 1 < n; ++i)
      ans = std::max(ans, (long long)l[i] * r[i + 1]);

    return ans;
  }

 private:
  static constexpr int kBase = 26;
  static constexpr int kMod = 1'000'000'007;

  // Returns true if s[l..r) is palindrome.
  bool isPalindrome(int l, int r, const vector<long>& hashFromL,
                    const vector<long>& hashFromR, const vector<long>& pow) {
    return leftHash(l, r, hashFromL, pow) == rightHash(l, r, hashFromR, pow);
  }

  // Returns hash of s[l..r) from left.
  long leftHash(int l, int r, const vector<long>& hashFromL,
                const vector<long>& pow) {
    const long hash = (hashFromL[r] - hashFromL[l] * pow[r - l]) % kMod;
    return hash < 0 ? hash + kMod : hash;
  }

  // Returns hash of s[l..r) from right.
  long rightHash(int l, int r, const vector<long>& hashFromR,
                 const vector<long>& pow) {
    const long hash = (hashFromR[l] - hashFromR[r] * pow[r - l]) % kMod;
    return hash < 0 ? hash + kMod : hash;
  }

  constexpr int val(char c) {
    return c - 'a';
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
  public long maxProduct(String s) {
    final int n = s.length();
    long ans = 1;
    long[] pow = new long[n + 1];       // pow[i] := kBase^i
    long[] hashFromL = new long[n + 1]; // hashFromL[i] = hash of s[0..i)
    long[] hashFromR = new long[n + 1]; // hashFromR[i] = hash of s[i..n)
    int[] l = new int[n];               // l[i] := max length of palindromes in s[0..i)
    int[] r = new int[n];               // r[i] := max length of palindromes in s[i..n)

    pow[0] = 1;
    for (int i = 1; i <= n; ++i)
      pow[i] = pow[i - 1] * kBase % kMod;

    for (int i = 1; i <= n; ++i)
      hashFromL[i] = (hashFromL[i - 1] * kBase + val(s.charAt(i - 1))) % kMod;

    for (int i = n - 1; i >= 0; --i)
      hashFromR[i] = (hashFromR[i + 1] * kBase + val(s.charAt(i))) % kMod;

    int max = 1; // max length of palindromes so far
    for (int i = 0; i < n; i++) {
      if (i - max - 1 >= 0 && isPalindrome(i - max - 1, i + 1, hashFromL, hashFromR, pow))
        max += 2;
      l[i] = max;
    }

    // Fill in r.
    max = 1;
    for (int i = n - 1; i >= 0; i--) {
      if (i + max + 2 <= n && isPalindrome(i, i + max + 2, hashFromL, hashFromR, pow))
        max += 2;
      r[i] = max;
    }

    for (int i = 0; i + 1 < n; ++i)
      ans = Math.max(ans, (long) l[i] * r[i + 1]);

    return ans;
  }

  private static final int kBase = 26;
  private static final int kMod = 1_000_000_007;

  // Returns true if s[l..r) is palindrome.
  private boolean isPalindrome(int l, int r, long[] hashFromL, long[] hashFromR, long[] pow) {
    return leftHash(l, r, hashFromL, pow) == rightHash(l, r, hashFromR, pow);
  }

  // Returns hash of s[l..r) from left.
  private long leftHash(int l, int r, long[] hashFromL, long[] pow) {
    final long hash = (hashFromL[r] - hashFromL[l] * pow[r - l]) % kMod;
    return hash < 0 ? hash + kMod : hash;
  }

  // Returns hash of s[l..r) from right.
  private long rightHash(int l, int r, long[] hashFromR, long[] pow) {
    final long hash = (hashFromR[l] - hashFromR[r] * pow[r - l]) % kMod;
    return hash < 0 ? hash + kMod : hash;
  }

  private int val(char c) {
    return c - 'a';
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution:
  def maxProduct(self, s: str) -> int:
    kBase = 26
    kMod = 1_000_000_007
    n = len(s)
    ans = 1
    pow = [1] + [0] * n  # pow[i] := kBase^i
    hashFromL = [0] * (n + 1)  # hashFromL[i] = hash of s[0..i)
    hashFromR = [0] * (n + 1)  # hashFromR[i] = hash of s[i..n)
    l = [0] * n  # l[i] := max length of palindromes in s[0..i)
    r = [0] * n  # r[i] := max length of palindromes in s[i..n)

    for i in range(1, n + 1):
      pow[i] = pow[i - 1] * kBase % kMod

    def val(c: str) -> int:
      return ord(c) - ord('a')

    for i in range(1, n + 1):
      hashFromL[i] = (hashFromL[i - 1] * kBase + val(s[i - 1])) % kMod

    for i in reversed(range(n)):
      hashFromR[i] = (hashFromR[i + 1] * kBase + val(s[i])) % kMod

    # Returns hash of s[l..r) from left.
    def leftHash(l: int, r: int) -> int:
      hash = (hashFromL[r] - hashFromL[l] * pow[r - l]) % kMod
      return hash + kMod if hash < 0 else hash

    # Returns hash of s[l..r) from right.
    def rightHash(l: int, r: int) -> int:
      hash = (hashFromR[l] - hashFromR[r] * pow[r - l]) % kMod
      return hash + kMod if hash < 0 else hash

    # Returns true if s[l..r) is palindrome.
    def isPalindrome(l: int, r: int) -> bool:
      return leftHash(l, r) == rightHash(l, r)

    maxi = 1  # max length of palindromes so far
    for i in range(n):
      if i - maxi - 1 >= 0 and isPalindrome(i - maxi - 1, i + 1):
        maxi += 2
      l[i] = maxi

    # Fill in r.
    maxi = 1
    for i in reversed(range(n)):
      if i + maxi + 2 <= n and isPalindrome(i, i + maxi + 2):
        maxi += 2
      r[i] = maxi

    for i in range(n - 1):
      ans = max(ans, l[i] * r[i + 1])

    return ans