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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Product of the Length of Two Palindromic Substrings

Difficulty: Hard

Problem Description

You are given a 0-indexed string s and are tasked with finding two non-intersecting palindromic substrings of odd length such that the product of their lengths is maximized. You need to return the maximum possible product of the lengths of the two non-intersecting palindromic substrings.

Key Insights

  • A palindrome reads the same forwards and backwards.
  • We need to find substrings of odd lengths that are also palindromic.
  • The two palindromic substrings must not overlap within the given string.
  • The goal is to maximize the product of the lengths of these two substrings.

Space and Time Complexity

Time Complexity: O(n^2) - due to the need to check for palindromic substrings in a nested loop. Space Complexity: O(n) - for storing the lengths of palindromic substrings.

Solution

The solution involves two main steps: identifying all possible odd-length palindromic substrings and then evaluating the maximum product of the lengths of two non-overlapping substrings.

  1. Finding Palindromic Substrings: We can use a center-expansion technique to find all odd-length palindromic substrings. For each character in the string, we expand around that character to check for palindromes.

  2. Calculating Maximum Product: After all palindromic substrings are identified, we can iterate through the list of palindromic lengths and, for each palindromic substring, check for the maximum product with non-overlapping substrings.

By maintaining a record of the longest palindromic substring lengths before and after each position, we can efficiently calculate the maximum product.

Code Solutions

def maxProduct(s: str) -> int:
    n = len(s)
    
    # Function to find all odd-length palindromic substrings
    def find_palindromes(s):
        pal_lengths = [0] * n
        for center in range(n):
            left, right = center, center
            while left >= 0 and right < n and s[left] == s[right]:
                pal_lengths[center] = max(pal_lengths[center], right - left + 1)
                left -= 1
                right += 1
        return pal_lengths
    
    pal_lengths = find_palindromes(s)
    
    # Calculate maximum product of two non-overlapping palindromic substrings
    max_product = 0
    max_length_before = [0] * n
    
    for i in range(n):
        if i > 0:
            max_length_before[i] = max(max_length_before[i - 1], pal_lengths[i - 1])
        
    for j in range(2, n):
        if pal_lengths[j] > 0:  # Check if there is a palindrome at j
            max_product = max(max_product, (pal_lengths[j] * max_length_before[j - 2]))
    
    return max_product
← Back to All Questions