We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Product of the Length of Two Palindromic Substrings

Number: 1336

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given a string s, find two non-intersecting odd-length palindromic substrings such that the product of their lengths is maximized. More formally, you need to choose indices i, j, k, l with 0 <= i <= j < k <= l < s.length so that both s[i...j] and s[k...l] are palindromes (each of odd length). Return the maximum product of their lengths.

Key Insights

  • Odd-length palindromes can be centered around each character. Use a method (like Manacher’s algorithm) to compute palindrome radii.
  • For every center, the maximum odd palindrome length is given by 2 * radius + 1.
  • Precompute two arrays:
    • left[i]: the maximum odd palindrome length ending at or before index i.
    • right[i]: the maximum odd palindrome length starting at or after index i.
  • The answer is obtained by considering all possible splits (non-intersecting condition) and maximizing left[j] * right[j+1].

Space and Time Complexity

Time Complexity: O(n), where n is the length of s (after using Manacher’s algorithm). Space Complexity: O(n) for storing the arrays of palindrome radii and the left/right maximum palindrome lengths.

Solution

We start by computing the palindrome radius for every center of the string using Manacher’s algorithm. Each center at index i gives a radius r such that the substring from i-r to i+r is a palindrome with odd length 2*r+1.

Next, we build:

  1. A left array where left[i] is defined as the maximum palindrome length among all palindromes ending at or before i. For a palindrome centered at i with radius r, it ends at i+r.
  2. A right array where right[i] is defined as the maximum palindrome length among all palindromes starting at or after i. For a palindrome centered at i with radius r, it starts at i-r.

After these precomputation steps, iterate over possible division points between the two substrings. For each valid split index j (where the first palindrome ends at or before j and the second starts at j+1), update the maximum product as left[j] * right[j+1].

Data Structures & Techniques:

  • An array to store the computed radius for each center using Manacher’s algorithm.
  • Two auxiliary arrays to keep track of the maximum odd palindrome lengths ending at or before an index (left) and starting at or after an index (right).
  • A final loop over the potential split index to determine the maximum product.

Important Gotchas:

  • Ensure palindromes are of odd length only.
  • Non-intersecting condition is guaranteed by considering a split between indices.

Code Solutions

# Python solution with detailed comments

def maxProduct(s: str) -> int:
    n = len(s)
    # Manacher's algorithm for odd-length palindromes only.
    # radius[i] is the maximum radius such that s[i-radius[i] : i+radius[i]+1] is a palindrome.
    radius = [0] * n
    center = 0
    right_bound = 0

    for i in range(n):
        mirror = 2 * center - i
        # Use previously computed radius if i is within the current palindrome boundary.
        if i < right_bound:
            radius[i] = min(radius[mirror], right_bound - i)
        # Expand the palindrome centered at i.
        while i - radius[i] - 1 >= 0 and i + radius[i] + 1 < n and s[i - radius[i] - 1] == s[i + radius[i] + 1]:
            radius[i] += 1
        # Update the center and right_bound if we expanded past the current boundary.
        if i + radius[i] > right_bound:
            center = i
            right_bound = i + radius[i]

    # left[i]: maximum odd palindrome length (2*radius+1) for any palindrome ending at or before i.
    left = [0] * n
    for i in range(n):
        # Calculate the end index of the palindrome with center i.
        p_len = 2 * radius[i] + 1
        end = i + radius[i]
        # Update left at the ending point.
        if end < n:
            left[end] = max(left[end], p_len)

    # Propagate the maximum values to the right.
    for i in range(1, n):
        left[i] = max(left[i], left[i-1])

    # right[i]: maximum odd palindrome length (2*radius+1) for any palindrome starting at or after i.
    right = [0] * n
    for i in range(n):
        p_len = 2 * radius[i] + 1
        start = i - radius[i]
        # Update right at the starting point.
        if start >= 0:
            right[start] = max(right[start], p_len)

    # Propagate maximum values from left-to-right in the right array.
    for i in range(n - 2, -1, -1):
        right[i] = max(right[i], right[i+1])

    # Compute the maximum product by splitting between indices.
    max_product = 0
    for split in range(n - 1):
        product = left[split] * right[split+1]
        max_product = max(max_product, product)
    return max_product

# Example usage:
print(maxProduct("ababbb"))  # Expected output: 9
← Back to All Questions