Problem Description

You are given a string s (0-indexed) and need to find two non-overlapping palindromic substrings, both with odd lengths, such that the product of their lengths is as large as possible.

The requirements are:

• Find two substrings s[i...j] and s[k...l] where the indices satisfy 0 <= i <= j < k <= l < s.length
• Both substrings must be palindromes (read the same forwards and backwards)
• Both substrings must have odd lengths
• The substrings cannot overlap (they are non-intersecting since j < k)
• Maximize the product of the two substring lengths

For example, if you have a string where you can find a palindrome of length 5 and another non-overlapping palindrome of length 3, their product would be 15.

The solution uses Manacher's algorithm to efficiently find all odd-length palindromes. It maintains:

• hlen[i]: the half-length of the longest odd palindrome centered at index i
• prefix[i]: the maximum odd palindrome length ending at or before index i
• suffix[i]: the maximum odd palindrome length starting at or after index i

The algorithm first computes all palindrome lengths using the expand-around-center technique with optimization. Then it builds prefix and suffix arrays to track the maximum palindrome lengths up to and from each position. Finally, it tries all possible split points to find two non-overlapping palindromes with maximum product.

Intuition

The key insight is that we need to find the best way to split the string into two parts where each part contains the longest possible odd-length palindrome. Since the palindromes cannot overlap, we can think of this as choosing a split point in the string.

First, we need to efficiently find all odd-length palindromes. Since we only care about odd-length palindromes, each one has a center character. For a character at position i, we can expand outward to find the longest palindrome centered at i. However, doing this naively for each position would be expensive.

This is where Manacher's algorithm comes in - it uses previously computed palindrome information to avoid redundant checks. If we've already found a long palindrome, and we're checking a position inside it, we can use symmetry to get a head start on our expansion.

Once we know all palindromes, the next challenge is: how do we efficiently find the best pair? We can't check all possible pairs as that would be too slow.

The breakthrough is realizing that for any split point i, we want:

• The longest palindrome that ends before position i (in the left part)
• The longest palindrome that starts from position i or after (in the right part)

This leads us to precompute two arrays:

• prefix[i]: maximum odd palindrome length in s[0...i]
• suffix[i]: maximum odd palindrome length in s[i...n-1]

But there's a subtle detail - a palindrome centered at position j with half-length h spans from j-h to j+h. So we need to carefully track where palindromes end and begin when building these arrays.

The final trick is handling the propagation of palindrome lengths. If there's a palindrome of length L ending at position i, there's also a palindrome of length L-2 ending at position i-1 (by removing one character from each end). This property helps us fill in the prefix and suffix arrays completely.

With these arrays ready, we simply try each split point and multiply the best palindrome length on the left with the best on the right, keeping track of the maximum product.

Solution Approach

The implementation consists of four main phases:

Phase 1: Find all odd-length palindromes using Manacher's Algorithm

The algorithm maintains hlen[i] which stores the half-length of the longest odd palindrome centered at index i. For example, if hlen[i] = 2, the palindrome spans from i-2 to i+2 with total length 5.

center = right = 0
for i in range(n):
    if i < right:
        hlen[i] = min(right - i, hlen[2 * center - i])

This optimization uses symmetry: if position i is within a known palindrome (centered at center with right boundary at right), we can initialize hlen[i] based on its mirror position 2 * center - i.

Then we expand around 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

Phase 2: Initialize prefix and suffix arrays

For each palindrome centered at i with half-length hlen[i]:

• It ends at position i + hlen[i], so we update prefix[i + hlen[i]]
• It starts at position i - hlen[i], so we update suffix[i - hlen[i]]
• The palindrome length is 2 * hlen[i] + 1

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)

Phase 3: Propagate palindrome lengths

If a palindrome of length L ends at position j, then a palindrome of length L-2 ends at position j-1 (by removing one character from each end).

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

The ~i notation means -(i+1), so we're iterating backwards through prefix array while iterating forwards through suffix array.

Phase 4: Compute cumulative maximums

Transform the arrays so that:

• prefix[i] = maximum palindrome length in range [0, i]
• suffix[i] = maximum palindrome length in range [i, n-1]

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

Phase 5: Find maximum product

For each possible split point i, multiply the best palindrome on the left (prefix[i-1]) with the best palindrome on the right (suffix[i]):

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

This ensures the two palindromes don't overlap since one ends before position i and the other starts at or after position i.

Example Walkthrough

Let's walk through the solution with the string s = "ababbb".

Phase 1: Find all odd-length palindromes

We calculate hlen[i] for each position:

• Position 0 ('a'): Expand around 'a' → Just 'a' itself → hlen[0] = 0
• Position 1 ('b'): Expand around 'b' → 'aba' works → hlen[1] = 1
• Position 2 ('a'): Expand around 'a' → 'bab' works → hlen[2] = 1
• Position 3 ('b'): Expand around 'b' → 'ababb' doesn't work, just 'b' → hlen[3] = 0
• Position 4 ('b'): Expand around 'b' → 'bbb' works → hlen[4] = 1
• Position 5 ('b'): Expand around 'b' → Just 'b' itself → hlen[5] = 0

So hlen = [0, 1, 1, 0, 1, 0]

Phase 2: Initialize prefix and suffix arrays

For each palindrome, mark where it ends (prefix) and starts (suffix):

• i=0: palindrome 'a' (length 1) ends at 0, starts at 0
  • prefix[0] = 1, suffix[0] = 1
• i=1: palindrome 'aba' (length 3) ends at 2, starts at 0
  • prefix[2] = 3, suffix[0] = max(1, 3) = 3
• i=2: palindrome 'bab' (length 3) ends at 3, starts at 1
  • prefix[3] = 3, suffix[1] = 3
• i=3: palindrome 'b' (length 1) ends at 3, starts at 3
  • prefix[3] = max(3, 1) = 3, suffix[3] = 1
• i=4: palindrome 'bbb' (length 3) ends at 5, starts at 3
  • prefix[5] = 3, suffix[3] = max(1, 3) = 3
• i=5: palindrome 'b' (length 1) ends at 5, starts at 5
  • prefix[5] = max(3, 1) = 3, suffix[5] = 1

Now: prefix = [1, 0, 3, 3, 0, 3], suffix = [3, 3, 0, 3, 0, 1]

Phase 3: Propagate palindrome lengths

If length L palindrome ends at j, then length L-2 ends at j-1:

• Working backwards in prefix:
  • prefix[4] = max(0, 3-2) = 1
  • prefix[3] = max(3, 1-2) = 3
  • prefix[2] = max(3, 3-2) = 3
  • prefix[1] = max(0, 3-2) = 1
  • prefix[0] = max(1, 1-2) = 1
• Working forwards in suffix:
  • suffix[1] = max(3, 3-2) = 3
  • suffix[2] = max(0, 3-2) = 1
  • suffix[3] = max(3, 1-2) = 3
  • suffix[4] = max(0, 3-2) = 1
  • suffix[5] = max(1, 1-2) = 1

Now: prefix = [1, 1, 3, 3, 1, 3], suffix = [3, 3, 1, 3, 1, 1]

Phase 4: Compute cumulative maximums

Transform to cumulative maximum arrays:

• Prefix (max so far): [1, 1, 3, 3, 3, 3]
• Suffix (max from here): [3, 3, 3, 3, 1, 1]

Phase 5: Find maximum product

Try each split point:

• Split at 1: prefix[0] * suffix[1] = 1 * 3 = 3
• Split at 2: prefix[1] * suffix[2] = 1 * 3 = 3
• Split at 3: prefix[2] * suffix[3] = 3 * 3 = 9 ✓
• Split at 4: prefix[3] * suffix[4] = 3 * 1 = 3
• Split at 5: prefix[4] * suffix[5] = 3 * 1 = 3

Maximum product is 9, achieved by splitting at position 3:

• Left part "aba" contains palindrome "aba" (length 3)
• Right part "bbb" contains palindrome "bbb" (length 3)
• Product: 3 × 3 = 9

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of several sequential phases, each taking linear time:

1. Manacher's Algorithm Phase: The main loop runs n iterations. While there's a nested while loop, each character in the string is visited at most twice due to the optimization with center and right boundaries. This phase is O(n).

2. Initial Prefix/Suffix Setup: A single loop of n iterations to populate initial values in prefix and suffix arrays based on palindrome half-lengths. This is O(n).

3. Backward Propagation: A loop from index 1 to n-1 that updates prefix and suffix arrays using the negative indexing trick (~i). This processes each element once, taking O(n).

4. Forward Accumulation: Another loop from index 1 to n-1 that computes the maximum values for prefix and suffix arrays by comparing with previous elements. This is O(n).

5. Final Maximum Calculation: A loop through n-1 elements to compute the maximum product of non-overlapping palindromes. This is O(n).

Total time complexity: O(n) + O(n) + O(n) + O(n) + O(n) = O(n)

Space Complexity: O(n)

The algorithm uses the following auxiliary data structures:

• hlen array of size n to store half-lengths of palindromes
• prefix array of size n to store maximum palindrome lengths up to each position
• suffix array of size n to store maximum palindrome lengths from each position
• A few constant variables (center, right, i)

Total space complexity: O(n) + O(n) + O(n) + O(1) = O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Errors in Boundary Handling

One of the most common mistakes is incorrectly handling the boundaries when initializing prefix and suffix arrays. Developers often confuse whether an index represents the end position or the position after the end of a palindrome.

Incorrect Implementation:

# Wrong: Using i + hlen[i] - 1 as the end position
prefix[i + hlen[i] - 1] = max(prefix[i + hlen[i] - 1], 2 * hlen[i] + 1)

Correct Implementation:

# Right: The palindrome ends exactly at position i + hlen[i]
prefix[i + hlen[i]] = max(prefix[i + hlen[i]], 2 * hlen[i] + 1)

2. Incorrect Palindrome Length Propagation

When propagating palindrome lengths inward, it's easy to forget that removing one character from each end reduces the length by 2, not 1. Also, the propagation direction matters.

Incorrect Implementation:

# Wrong: Decrementing by 1 instead of 2
for i in range(1, n):
    prefix[i] = max(prefix[i], prefix[i - 1] - 1)
  
# Wrong: Propagating in the wrong direction
for i in range(1, n):
    prefix[i] = max(prefix[i], prefix[i - 1] - 2)  # Should go backward

Correct Implementation:

# Propagate backward for prefix (from right to left)
# Propagate forward for suffix (from left to right)
for i in range(1, n):
    prefix[n - 1 - i] = max(prefix[n - 1 - i], prefix[n - i] - 2)
    suffix[i] = max(suffix[i], suffix[i - 1] - 2)

3. Missing Cumulative Maximum Calculation

A critical mistake is forgetting to transform the prefix and suffix arrays into cumulative maximums. Without this step, you only have palindromes at specific positions, not the best palindromes in ranges.

Incorrect Implementation:

# Wrong: Using prefix/suffix arrays directly without cumulative max
max_product = 0
for i in range(1, n):
    # This only considers palindromes ending exactly at i-1 
    # and starting exactly at i
    product = prefix[i - 1] * suffix[i]
    max_product = max(max_product, product)

Correct Implementation:

# Transform to cumulative maximums first
for i in range(1, n):
    prefix[i] = max(prefix[i - 1], prefix[i])
    suffix[n - 1 - i] = max(suffix[n - 1 - i], suffix[n - i])

# Now prefix[i] contains the best palindrome in [0, i]
# and suffix[i] contains the best palindrome in [i, n-1]

4. Manacher's Algorithm Boundary Check Errors

When expanding palindromes, forgetting to check both boundaries can lead to index out of bounds errors.

Incorrect Implementation:

# Wrong: Missing boundary checks
while s[i - 1 - half_lengths[i]] == s[i + 1 + half_lengths[i]]:
    half_lengths[i] += 1

Correct Implementation:

# Include proper boundary checks
while (0 <= i - 1 - half_lengths[i] and 
       i + 1 + half_lengths[i] < n and 
       s[i - 1 - half_lengths[i]] == s[i + 1 + half_lengths[i]]):
    half_lengths[i] += 1

5. Confusion with the ~i Notation

The tilde operator ~i equals -(i+1), which when used as an array index in Python, accesses elements from the end. This can be confusing and lead to errors.

Alternative Clear Implementation:

# Instead of using ~i, be explicit:
for i in range(1, n):
    idx = n - 1 - i  # Clear backward iteration
    prefix[idx] = max(prefix[idx], prefix[idx + 1] - 2)
    suffix[i] = max(suffix[i], suffix[i - 1] - 2)

Prevention Tips:

1. Draw out small examples and trace through the array indices manually
2. Use descriptive variable names like end_pos and start_pos instead of just i + hlen[i]
3. Add assertions or debug prints to verify array bounds during development
4. Test with edge cases like single character strings and strings with no palindromes