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
44
class Solution {
 public:
  long long maxProduct(string s) {
    const int n = s.length();
    long ans = 1;
    // maxLeft[i] := the maximum odd length of palindromes in s[0..i]
    vector<int> maxLeft = manacher(s, n);
    // maxRight[i] := the maximum odd length of palindromes in s[i..n - 1]
    vector<int> maxRight = manacher(string{s.rbegin(), s.rend()}, n);

    ranges::reverse(maxRight);

    for (int i = 1; i < n; ++i)
      ans = max(ans, static_cast<long>(maxLeft[i - 1]) * maxRight[i]);

    return ans;
  }

 private:
  vector<int> manacher(const string& s, int n) {
    vector<int> maxExtends(n);
    vector<int> leftToRight(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]) {
        leftToRight[i + extend] = 2 * extend + 1;
        ++extend;
      }
      maxExtends[i] = extend;
      if (i + maxExtends[i] >= r)
        center = i;
    }

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

    return leftToRight;
  }
};

 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;
    // maxLeft[i] := the maximum odd length of palindromes in s[0..i]
    int[] maxLeft = manacher(s, n);
    // maxRight[i] := the maximum odd length of palindromes in s[i..n - 1]
    int[] maxRight = manacher(new StringBuilder(s).reverse().toString(), n);

    reverse(maxRight, 0, n - 1);

    for (int i = 1; i < n; ++i)
      ans = Math.max(ans, (long) maxLeft[i - 1] * maxRight[i]);

    return ans;
  }

  private int[] manacher(final String s, int n) {
    int[] maxExtends = new int[n];
    int[] leftToRight = new int[n];
    Arrays.fill(leftToRight, 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)) {
        leftToRight[i + extend] = 2 * extend + 1;
        ++extend;
      }
      maxExtends[i] = extend;
      if (i + maxExtends[i] >= r)
        center = i;
    }

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

    return leftToRight;
  }

  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
      leftToRight = [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]:
          leftToRight[i + extend] = 2 * extend + 1
          extend += 1
        maxExtends[i] = extend
        if i + maxExtends[i] >= r:
          center = i

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

      return leftToRight

    # maxLeft[i] := the maximum odd length of palindromes in s[0..i]
    maxLeft = manacher(s)
    # maxRight[i] := the maximum odd length of palindromes in s[i..n - 1]
    maxRight = manacher(s[::-1])[::-1]
    return max(maxLeft[i - 1] * maxRight[i] for i in range(1, n))

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
73
74
75
76
77
78
79
class Solution {
 public:
  long long maxProduct(string s) {
    const int n = s.length();
    long ans = 1;
    vector<long> pows{1};  // pows[i] := kBase^i % kHash
    // hashL[i] = the hash of the first i letters of s, where hashL[i] =
    // (26^(i - 1) * s[0] + 26^(i - 2) * s[1] + ... + s[i - 1]) % kHash
    vector<long> hashL{0};
    // hashR[i] = the hash of the last i letters of s, where hashR[i] =
    // (26^(i - 1) * s[-1] + 26^(i - 2) * s[-2] + ... + s[-i]) % kHash
    vector<long> hashR{0};
    // maxLeft[i] := the maximum odd length of palindromes in s[0..i]
    vector<int> maxLeft(n);
    // maxRight[i] := the maximum odd length of palindromes in s[i..n - 1]
    vector<int> maxRight(n);

    for (int i = 0; i < n; ++i)
      pows.push_back(pows.back() * kBase % kHash);

    for (int i = 0; i < n; ++i)
      hashL.push_back((hashL.back() * kBase + val(s[i])) % kHash);

    for (int i = n - 1; i >= 0; --i)
      hashR.push_back((hashR.back() * kBase + val(s[i])) % kHash);

    ranges::reverse(hashR);

    int maxLength = 1;
    for (int r = 0; r < n; ++r) {
      const int l = (r - maxLength - 2) + 1;
      if (l >= 0 && isPalindrome(l, r + 1, hashL, hashR, pows))
        maxLength += 2;
      maxLeft[r] = maxLength;
    }

    maxLength = 1;
    for (int l = n - 1; l >= 0; --l) {
      const int r = (l + maxLength + 2) - 1;
      if (r < n && isPalindrome(l, r + 1, hashL, hashR, pows))
        maxLength += 2;
      maxRight[l] = maxLength;
    }

    for (int i = 1; i < n; ++i)
      ans = max(ans, static_cast<long>(maxLeft[i - 1]) * maxRight[i]);

    return ans;
  }

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

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

  // Returns true if s[l..r) is a palindrome.
  bool isPalindrome(int l, int r, const vector<long>& hashL,
                    const vector<long>& hashR, const vector<long>& pows) {
    return getLeftRollingHash(l, r, hashL, pows) ==
           getRightRollingHash(l, r, hashR, pows);
  }

  // Returns the left rolling hash of s[l..r).
  long getLeftRollingHash(int l, int r, const vector<long>& hashL,
                          const vector<long>& pows) {
    const long h = (hashL[r] - hashL[l] * pows[r - l]) % kHash;
    return h < 0 ? h + kHash : h;
  }

  // Returns the right rolling hash of s[l..r).
  long getRightRollingHash(int l, int r, const vector<long>& hashR,
                           const vector<long>& pows) {
    const long h = (hashR[l] - hashR[r] * pows[r - l]) % kHash;
    return h < 0 ? h + kHash : h;
  }
};

 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 maxProduct(String s) {
    final int n = s.length();
    long ans = 1;
    long[] pows = new long[n + 1]; // pows[i] := kBase^i % kHash
    // hashL[i] = the hash of the first i letters of s, where hashL[i] =
    // (26^(i - 1) * s[0] + 26^(i - 2) * s[1] + ... + s[i - 1]) % kHash
    long[] hashL = new long[n + 1];
    // hashR[i] = the hash of the last i letters of s, where hashR[i] =
    // (26^(i - 1) * s[-1] + 26^(i - 2) * s[-2] + ... + s[-i]) % kHash
    long[] hashR = new long[n + 1];
    // maxLeft[i] := the maximum odd length of palindromes in s[0..i]
    int[] maxLeft = new int[n];
    // maxRight[i] := the maximum odd length of palindromes in s[i..n - 1]
    int[] maxRight = new int[n];

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

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

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

    int maxLength = 1;
    for (int r = 0; r < n; ++r) {
      final int l = (r - maxLength - 2) + 1;
      if (l >= 0 && isPalindrome(l, r + 1, hashL, hashR, pows))
        maxLength += 2;
      maxLeft[r] = maxLength;
    }

    maxLength = 1;
    for (int l = n - 1; l >= 0; --l) {
      final int r = (l + maxLength + 2) - 1;
      if (r < n && isPalindrome(l, r + 1, hashL, hashR, pows))
        maxLength += 2;
      maxRight[l] = maxLength;
    }

    for (int i = 1; i < n; ++i)
      ans = Math.max(ans, (long) maxLeft[i - 1] * maxRight[i]);

    return ans;
  }

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

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

  // Returns true if s[l..r) is a palindrome.
  private boolean isPalindrome(int l, int r, long[] hashL, long[] hashR, long[] pows) {
    return getLeftRollingHash(l, r, hashL, pows) == getRightRollingHash(l, r, hashR, pows);
  }

  // Returns the left rolling hash of s[l..r).
  private long getLeftRollingHash(int l, int r, long[] hashL, long[] pows) {
    final long h = (hashL[r] - hashL[l] * pows[r - l]) % kHash;
    return h < 0 ? h + kHash : h;
  }

  // Returns the right rolling hash of s[l..r).
  private long getRightRollingHash(int l, int r, long[] hashR, long[] pows) {
    final long h = (hashR[l] - hashR[r] * pows[r - l]) % kHash;
    return h < 0 ? h + kHash : h;
  }
}

 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
class Solution:
  def maxProduct(self, s: str) -> int:
    kBase = 26
    kHash = 1_000_000_007
    n = len(s)
    pows = [1]  # pows[i] := kBase^i % kHash
    # hashL[i] = the hash of the first i letters of s, where hashL[i] =
    # (26^(i - 1) * s[0] + 26^(i - 2) * s[1] + ... + s[i - 1]) % kHash
    hashL = [0]
    # hashR[i] = the hash of the last i letters of s, where hashR[i] =
    # (26^(i - 1) * s[-1] + 26^(i - 2) * s[-2] + ... + s[-i]) % kHash
    hashR = [0]
    # maxLeft[i] := the maximum odd length of palindromes in s[0..i]
    maxLeft = [0] * n
    # maxRight[i] := the maximum odd length of palindromes in s[i..n - 1]
    maxRight = [0] * n

    def val(c: str) -> int:
      return string.ascii_lowercase.index(c)

    for _ in range(n):
      pows.append(pows[-1] * kBase % kHash)

    for c in s:
      hashL.append((hashL[-1] * kBase + val(c)) % kHash)

    for c in reversed(s):
      hashR.append((hashR[-1] * kBase + val(c)) % kHash)

    hashR.reverse()

    def getLeftRollingHash(l: int, r: int) -> int:
      """Returns the left rolling hash of s[l..r)."""
      h = (hashL[r] - hashL[l] * pows[r - l]) % kHash
      return h + kHash if h < 0 else h

    def getRightRollingHash(l: int, r: int) -> int:
      """Returns the right rolling hash of s[l..r)."""
      h = (hashR[l] - hashR[r] * pows[r - l]) % kHash
      return h + kHash if h < 0 else h

    def isPalindrome(l: int, r: int) -> bool:
      """Returns True if s[l..r) is a palindrome."""
      return getLeftRollingHash(l, r) == getRightRollingHash(l, r)

    maxLength = 1
    for r in range(n):
      l = (r - maxLength - 2) + 1
      if l >= 0 and isPalindrome(l, r + 1):
        maxLength += 2
      maxLeft[r] = maxLength

    maxLength = 1
    for l in reversed(range(n)):
      r = (l + maxLength + 2) - 1
      if r < n and isPalindrome(l, r + 1):
        maxLength += 2
      maxRight[l] = maxLength

    return max(maxLeft[i - 1] * maxRight[i] for i in range(1, n))