#1960

Hard

LeetCode Problem Workspace

Maximum Product of the Length of Two Palindromic Substrings

Find the maximum product of lengths of two non-overlapping odd-length palindromic substrings using string and rolling hash techniques.

string rolling hash hash function

Problem Statement

Given a string s, find two non-overlapping palindromic substrings with odd lengths such that the product of their lengths is maximized. Each substring must have at least one character, and their positions cannot intersect.

Formally, choose integers i, j, k, l where 0 <= i <= j < k <= l < s.length, and both s[i...j] and s[k...l] are odd-length palindromes. Return the maximum product of these two palindrome lengths.

Examples

Example 1

Input: s = "ababbb"

Output: 9

Substrings "aba" and "bbb" are palindromes with odd length. product = 3 * 3 = 9.

Example 2

Input: s = "zaaaxbbby"

Output: 9

Substrings "aaa" and "bbb" are palindromes with odd length. product = 3 * 3 = 9.

Constraints

2 <= s.length <= 105
s consists of lowercase English letters.

Solution Approach

Use Manacher's Algorithm

Apply Manacher's algorithm to compute the maximum palindrome radius for each center efficiently. This generates all odd-length palindromes in linear time, providing a foundation to evaluate potential substring pairs without redundant checks.

Compute Maximum Prefix and Suffix Lengths

Construct arrays for the largest palindromic substring ending at each index and starting at each index. This allows fast lookup of the best candidate palindrome to the left and right of any split point, directly optimizing the product calculation.

Combine Non-Overlapping Palindromes

Iterate through possible split points to select one palindrome from the prefix and one from the suffix. Compute the product and track the maximum. Rolling hash can verify palindromes quickly when needed, ensuring correct comparisons.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) using Manacher's algorithm to generate palindromes and O(n) to combine prefix and suffix maximums. Space complexity is O(n) for storing radii and prefix/suffix arrays.

What Interviewers Usually Probe

Check if candidate palindromes overlap before computing the product.
Consider using rolling hash for substring verification if needed.
Observe that only odd-length palindromes are relevant; even lengths are ignored.

Common Pitfalls or Variants

Common pitfalls

Counting even-length palindromes mistakenly, which violates the problem constraint.
Overlapping substrings causing invalid product calculations.
Using nested loops to compare all palindrome pairs, which is too slow for large strings.

Follow-up variants

Maximize the sum of lengths instead of the product of two non-overlapping odd-length palindromes.
Consider even-length palindromes alongside odd-length palindromes for maximum product.
Restrict palindromes to a minimum length k, requiring adjusted prefix/suffix calculations.

FAQ

What is the best approach for Maximum Product of the Length of Two Palindromic Substrings?

Use Manacher's algorithm to get all odd-length palindromes and combine prefix and suffix maximums to compute the product efficiently.

Can even-length palindromes be used in this problem?

No, the problem specifically requires palindromic substrings of odd length only.

How does rolling hash help in this problem?

Rolling hash can quickly verify substring palindromes when combining candidates, reducing repeated character comparisons.

What is the time complexity of the optimal solution?

Using Manacher's algorithm and prefix/suffix arrays, the solution runs in O(n) time and O(n) space.

How do I avoid overlapping palindromes?

Use prefix and suffix maximum arrays and only combine palindromes that are separated by at least one index to ensure no overlap.

terminal

Solution

Solution 1

#### Python3

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

class Solution:
    def maxProduct(self, s: str) -> int:
        n = len(s)
        hlen = [0] * n
        center = right = 0

        for i in range(n):
            if i < right:
                hlen[i] = min(right - i, hlen[2 * center - i])
            while (
                0 <= i - 1 - hlen[i]
                and i + 1 + hlen[i] < len(s)
                and s[i - 1 - hlen[i]] == s[i + 1 + hlen[i]]
            ):
                hlen[i] += 1
            if right < i + hlen[i]:
                center, right = i, i + hlen[i]

        prefix = [0] * n
        suffix = [0] * n

        for i in range(n):
            prefix[i + hlen[i]] = max(prefix[i + hlen[i]], 2 * hlen[i] + 1)
            suffix[i - hlen[i]] = max(suffix[i - hlen[i]], 2 * hlen[i] + 1)

        for i in range(1, n):
            prefix[~i] = max(prefix[~i], prefix[~i + 1] - 2)
            suffix[i] = max(suffix[i], suffix[i - 1] - 2)

        for i in range(1, n):
            prefix[i] = max(prefix[i - 1], prefix[i])
            suffix[~i] = max(suffix[~i], suffix[~i + 1])

        return max(prefix[i - 1] * suffix[i] for i in range(1, n))

Continue Practicing

#2156 find substring with given hash value #2223 sum of scores of built strings #2430 maximum deletions on a string