LeetCode 1960 - Maximum Product of the Length of Two Palindromic Substrings

The problem asks us to find two non-overlapping odd-length palindromic substrings whose length product is as large as possible. We are given a string s of length up to 10^5.

leetcodehardtwo-pointersstringrolling-hashhash-function

LeetCode Problem 1960

Difficulty: 🔴 Hard
Topics: Two Pointers, String, Rolling Hash, Hash Function

Solution

LeetCode 1960 - Maximum Product of the Length of Two Palindromic Substrings

Problem Understanding

The problem asks us to find two non-overlapping odd-length palindromic substrings whose length product is as large as possible.

We are given a string s of length up to 10^5. We must choose two palindromic substrings:

  • The first occupies indices [i, j]
  • The second occupies indices [k, l]
  • They must not intersect, so j < k
  • Both palindrome lengths must be odd

Our goal is to maximize:

$$(j - i + 1) \times (l - k + 1)$$

The key observation is that the two palindromes only need to be separated by some split point. If we knew:

  • The longest odd palindrome completely contained in every prefix.
  • The longest odd palindrome completely contained in every suffix.

Then every split position could be evaluated independently.

The constraints are the most important part of the problem. Since:

$$n \le 10^5$$

any solution worse than approximately O(n log n) is likely too slow. Enumerating all palindromes or all substring pairs is impossible because there are O(n²) substrings and O(n⁴) pairs of substrings.

Important edge cases include:

  • Strings where every character is the same, producing extremely large overlapping palindromes.
  • Strings with no palindrome longer than length 1.
  • Cases where the optimal answer uses a shorter palindrome because a larger one blocks a better second palindrome.
  • Very long strings near the constraint limit, requiring a linear or near-linear algorithm.

Problem Understanding

The problem asks us to find two non-overlapping palindromic substrings of odd length in a given string s such that the product of their lengths is maximized. Essentially, we are tasked with identifying the largest “odd-length palindromes” in two separate parts of the string and computing the maximum product of their lengths.

The input is a string of lowercase English letters with length up to 10^5. The output is a single integer representing the maximum product. The key constraints are that palindromes must be odd in length and non-intersecting, which rules out any naive approach that tries all substrings, because the number of substrings scales quadratically with string length.

Edge cases include strings where all characters are the same, strings without any palindromes longer than 1, and strings of minimum length (2). The constraints guarantee at least two characters, so we always have the minimal opportunity to form two palindromes of length 1.

Approaches

Brute Force

A direct approach would enumerate every odd-length palindrome in the string, then examine every pair of palindromes and compute the product whenever they do not overlap.

This is correct because every valid solution is explicitly checked. Unfortunately, there can be O(n²) palindromic substrings in a string such as "aaaaaa...". Comparing all pairs would require O(n⁴) time in the worst case.

Even a more careful implementation that first enumerates all palindromes and then checks pairs remains far too slow for n = 10^5.

Key Insight

The critical observation is that the final answer is determined by some split position.

Suppose we split the string between indices i and i+1.

Then:

  • The left palindrome must lie entirely inside [0, i].
  • The right palindrome must lie entirely inside [i+1, n-1].

If we know:

  • left[i] = longest odd palindrome fully contained in prefix [0, i]
  • right[i] = longest odd palindrome fully contained in suffix [i, n-1]

then the answer becomes:

$$\max_i \left(left[i] \times right[i+1]\right)$$

The remaining challenge is computing these arrays efficiently.

This is where Manacher's algorithm becomes useful. It computes, for every center, the maximum odd palindrome radius in linear time.

From those radii, we can determine which palindrome lengths end at each position and which start at each position. Using a sweep with a priority queue, we can compute the longest palindrome available at every index in O(n log n) time.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n⁴) O(n²) Enumerate all palindrome pairs
Optimal O(n log n) O(n) Manacher + sweep line + prefix/suffix maxima

Algorithm Walkthrough

1. Compute odd palindrome radii using Manacher's algorithm

For every position i, compute:

$$d[i]$$

where d[i] is the radius of the largest odd palindrome centered at i.

The palindrome length is:

$$2d[i]-1$$

Manacher computes all radii in O(n) time.

2. Record palindrome intervals

For each center i:

  • Left boundary:

$$L=i-d[i]+1$$

  • Right boundary:

$$R=i+d[i]-1$$

  • Length:

$$len=2d[i]-1$$

This largest palindrome implicitly contains all smaller odd palindromes centered at the same position.

3. Compute longest palindrome ending at every position

For a palindrome centered at c with radius r:

$$R=c+r-1$$

Every palindrome ending at position x ≤ R contributes:

$$2(x-c)+1$$

which grows linearly as x moves right.

A sweep line processes centers whose palindrome currently covers position x.

A max-heap stores:

$$2x + (-2c + 1)$$

allowing the best palindrome ending at each position to be obtained efficiently.

Store the result in:

endBest[x]

4. Convert to best palindrome contained in each prefix

If a palindrome ends at position x, then it is contained in every later prefix.

Therefore:

left[i] = max(left[i-1], endBest[i])

Now left[i] represents the longest palindrome fully inside prefix [0, i].

5. Compute longest palindrome starting at every position

Apply the symmetric process from right to left.

Store:

startBest[i]

which is the longest palindrome starting exactly at i.

6. Convert to best palindrome contained in each suffix

If a palindrome starts at position i, it belongs to every suffix beginning before i.

Compute:

right[i] = max(right[i+1], startBest[i])

Now right[i] is the longest palindrome fully contained in suffix [i, n-1].

7. Evaluate every split

For every split between i and i+1:

left[i] * right[i+1]

Take the maximum value.

Why it works

Manacher's algorithm guarantees that every odd palindrome is represented by some center radius. The sweep-line computations derive the maximum palindrome length ending or starting at every position without explicitly enumerating all palindromes. The prefix and suffix maxima then ensure that for every split position we know the best palindrome entirely on the left and entirely on the right. Since every valid pair of non-overlapping palindromes must be separated by some split, checking all splits guarantees that the maximum product is found. The brute-force approach would iterate over all possible pairs of substrings (s[i:j+1], s[k:l+1]), check if they are odd-length palindromes, ensure they do not overlap, and compute the product of their lengths. This approach is correct but infeasible because for a string of length n, the number of substrings is O(n^2), and checking if a substring is a palindrome is O(n). This leads to a total time complexity of roughly O(n^4).

Optimal Approach

The key observation is that we only need odd-length palindromes, which allows us to use Manacher's algorithm to find the maximum odd-length palindrome centered at each character in O(n) time. Once we have the longest palindromes centered at each index, we can precompute two arrays:

  1. left[i]: the length of the longest odd-length palindrome ending at or before index i.
  2. right[i]: the length of the longest odd-length palindrome starting at or after index i.

Then, for each possible split point in the string, the maximum product is left[i] * right[i+1]. This reduces the problem to linear time after the initial palindrome computation.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^4) O(1) Check all substring pairs
Optimal O(n) O(n) Use Manacher's algorithm and prefix/suffix max arrays

Algorithm Walkthrough

  1. Use Manacher's algorithm to compute odd_pal_len[i] for each center i, which represents the maximum radius of an odd-length palindrome centered at i.
  2. Initialize arrays left_max and right_max of size n. left_max[i] will hold the length of the longest odd-length palindrome ending at or before i. right_max[i] will hold the length of the longest odd-length palindrome starting at or after i.
  3. Iterate through the string to fill left_max. For each palindrome centered at i with radius r, update the maximum length for all indices covered by this palindrome.
  4. Similarly, iterate backwards to fill right_max.
  5. Compute the maximum product by iterating over all split points i from 0 to n-2 and calculate left_max[i] * right_max[i+1].
  6. Return the maximum product.

Why it works: Manacher's algorithm guarantees that we know the largest palindrome centered at every index in linear time. Using prefix and suffix max arrays ensures that for any split, we can efficiently compute the maximum product of two non-intersecting palindromes.

Python Solution

from typing import List
import heapq

class Solution:
    def maxProduct(self, s: str) -> int:
        n = len(s)

        # Manacher for odd palindromes
        d = [0] * n
        l = 0
        r = -1

        for i in range(n):
            k = 1 if i > r else min(d[l + r - i], r - i + 1)

            while (
                i - k >= 0
                and i + k < n
                and s[i - k] == s[i + k]
            ):
                k += 1

            d[i] = k

            if i + k - 1 > r:
                l = i - k + 1
                r = i + k - 1

        # longest palindrome ending at each position
        add_end = [[] for _ in range(n)]
        remove_end = [[] for _ in range(n + 1)]

        for c, rad in enumerate(d):
            start = c
            end = c + rad - 1

            add_end[start].append(c)

            if end + 1 < len(remove_end):
                remove_end[end + 1].append(c)

        heap = []
        removed = {}

        end_best = [1] * n

        for pos in range(n):
            for c in add_end[pos]:
                value = -2 * c + 1
                heapq.heappush(heap, (-value, c))

            for c in remove_end[pos]:
                removed[c] = removed.get(c, 0) + 1

            while heap:
                _, c = heap[0]
                if removed.get(c, 0):
                    removed[c] -= 1
                    heapq.heappop(heap)
                else:
                    break

            if heap:
                value = -heap[0][0]
                end_best[pos] = 2 * pos + value

        left = [0] * n
        left[0] = end_best[0]

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

        # longest palindrome starting at each position
        add_start = [[] for _ in range(n)]
        remove_start = [[] for _ in range(n + 1)]

        for c, rad in enumerate(d):
            start = c - rad + 1
            end = c

            add_start[end].append(c)

            if start - 1 >= 0:
                remove_start[start - 1].append(c)

        heap = []
        removed = {}

        start_best = [1] * n

        for pos in range(n - 1, -1, -1):
            for c in add_start[pos]:
                value = 2 * c + 1
                heapq.heappush(heap, (-value, c))

            for c in remove_start[pos]:
                removed[c] = removed.get(c, 0) + 1

            while heap:
                _, c = heap[0]
                if removed.get(c, 0):
                    removed[c] -= 1
                    heapq.heappop(heap)
                else:
                    break

            if heap:
                value = -heap[0][0]
                start_best[pos] = value - 2 * pos

        right = [0] * n
        right[-1] = start_best[-1]

        for i in range(n - 2, -1, -1):
            right[i] = max(right[i + 1], start_best[i])

        answer = 0

        for i in range(n - 1):
            answer = max(answer, left[i] * right[i + 1])

        return answer

Implementation Explanation

The first section implements Manacher's algorithm and computes the maximum odd palindrome radius around every center. This provides all palindrome information in linear time.

The next sweep computes end_best. Every palindrome contributes a linear function describing the largest palindrome ending at each reachable position. A heap maintains the currently active centers, allowing the maximum value to be retrieved efficiently.

The prefix maximum pass transforms these exact ending lengths into left[i], the best palindrome fully contained in each prefix.

The process is then mirrored from right to left to compute start_best, followed by a suffix maximum pass to produce right[i].

Finally, every split position is evaluated. The left side contributes left[i], the right side contributes right[i+1], and the maximum product is returned. class Solution: def maxProduct(self, s: str) -> int: n = len(s)

    # Step 1: Manacher's algorithm for odd-length palindromes
    odd_len = [0] * n
    center, right = 0, 0
    for i in range(n):
        mirror = 2 * center - i
        if i < right:
            odd_len[i] = min(right - i, odd_len[mirror])
        a, b = i - (odd_len[i] + 1), i + (odd_len[i] + 1)
        while a >= 0 and b < n and s[a] == s[b]:
            odd_len[i] += 1
            a -= 1
            b += 1
        if i + odd_len[i] > right:
            center, right = i, i + odd_len[i]
    
    # Step 2: Build left_max and right_max arrays
    left_max = [0] * n
    right_max = [0] * n
    
    for i in range(n):
        length = 2 * odd_len[i] + 1
        start = i - odd_len[i]
        end = i + odd_len[i]
        left_max[end] = max(left_max[end], length)
        right_max[start] = max(right_max[start], length)
    
    for i in range(1, n):
        left_max[i] = max(left_max[i], left_max[i-1])
    for i in range(n-2, -1, -1):
        right_max[i] = max(right_max[i], right_max[i+1])
    
    # Step 3: Compute maximum product
    max_prod = 0
    for i in range(n-1):
        max_prod = max(max_prod, left_max[i] * right_max[i+1])
    
    return max_prod


**Explanation:** We first compute all odd-length palindromes with Manacher’s algorithm. Then we build `left_max` and `right_max` to efficiently find the largest palindromes on each side of any split. Finally, we iterate over split points to get the maximum product.

## Go Solution

```go
package main

import "container/heap"

type Item struct {
	value  int
	center int
}

type MaxHeap []Item

func (h MaxHeap) Len() int { return len(h) }
func (h MaxHeap) Less(i, j int) bool {
	return h[i].value > h[j].value
}
func (h MaxHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}
func (h *MaxHeap) Push(x interface{}) {
	*h = append(*h, x.(Item))
}
func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[:n-1]
	return item
}

func maxProduct(s string) int64 {
	n := len(s)

	d := make([]int, n)

	l, r := 0, -1

	for i := 0; i < n; i++ {
		k := 1

		if i <= r {
			mirror := l + r - i
			if d[mirror] < r-i+1 {
				k = d[mirror]
			} else {
				k = r - i + 1
			}
		}

		for i-k >= 0 && i+k < n && s[i-k] == s[i+k] {
			k++
		}

		d[i] = k

		if i+k-1 > r {
			l = i - k + 1
			r = i + k - 1
		}
	}

	addEnd := make([][]int, n)
	removeEnd := make([][]int, n+1)

	for c, rad := range d {
		start := c
		end := c + rad - 1

		addEnd[start] = append(addEnd[start], c)

		if end+1 < len(removeEnd) {
			removeEnd[end+1] = append(removeEnd[end+1], c)
		}
	}

	endBest := make([]int, n)
	removed := map[int]int{}

	h := &MaxHeap{}
	heap.Init(h)

	for pos := 0; pos < n; pos++ {
		for _, c := range addEnd[pos] {
			heap.Push(h, Item{
				value:  -2*c + 1,
				center: c,
			})
		}

		for _, c := range removeEnd[pos] {
			removed[c]++
		}

		for h.Len() > 0 {
			top := (*h)[0]
			if removed[top.center] > 0 {
				removed[top.center]--
				heap.Pop(h)
			} else {
				break
			}
		}

		endBest[pos] = 1

		if h.Len() > 0 {
			endBest[pos] = 2*pos + (*h)[0].value
		}
	}

	left := make([]int, n)
	left[0] = endBest[0]

	for i := 1; i < n; i++ {
		if left[i-1] > endBest[i] {
			left[i] = left[i-1]
		} else {
			left[i] = endBest[i]
		}
	}

	addStart := make([][]int, n)
	removeStart := make([][]int, n+1)

	for c, rad := range d {
		start := c - rad + 1
		end := c

		addStart[end] = append(addStart[end], c)

		if start-1 >= 0 {
			removeStart[start-1] = append(removeStart[start-1], c)
		}
	}

	startBest := make([]int, n)
	removed = map[int]int{}

	h = &MaxHeap{}
	heap.Init(h)

	for pos := n - 1; pos >= 0; pos-- {
		for _, c := range addStart[pos] {
			heap.Push(h, Item{
				value: 2*c + 1,
				center: c,
			})
		}

		for _, c := range removeStart[pos] {
			removed[c]++
		}

		for h.Len() > 0 {
			top := (*h)[0]
			if removed[top.center] > 0 {
				removed[top.center]--
				heap.Pop(h)
			} else {
				break
			}
		}

		startBest[pos] = 1

		if h.Len() > 0 {
			startBest[pos] = (*h)[0].value - 2*pos
		}
	}

	right := make([]int, n)
	right[n-1] = startBest[n-1]

	for i := n - 2; i >= 0; i-- {
		if right[i+1] > startBest[i] {
			right[i] = right[i+1]
		} else {
			right[i] = startBest[i]
		}
	}

	var ans int64

	for i := 0; i < n-1; i++ {
		product := int64(left[i]) * int64(right[i+1])

		if product > ans {
			ans = product
		}
	}

	return ans
}

Go-Specific Notes

The Go implementation mirrors the Python solution closely. A custom max-heap is implemented using container/heap. The final answer uses int64 because the product can reach approximately:

$$10^5 \times 10^5 = 10^{10}$$

which exceeds the range of a 32-bit integer.

Worked Examples

Example 1

Input:

s = "ababbb"

Manacher radii:

Index Character Radius Longest Odd Length
0 a 1 1
1 b 2 3
2 a 2 3
3 b 1 1
4 b 1 1
5 b 1 1

After processing:

Position left
0 1
1 1
2 3
3 3
4 3
5 3
Position right
0 3
1 3
2 3
3 3
4 1
5 1

Split evaluation:

Split After Product
0 1×3=3
1 1×3=3
2 3×3=9
3 3×1=3
4 3×1=3

Maximum:

9

Example 2

Input:

s = "zaaaxbbby"

Relevant palindromes:

"aaa" length 3
"bbb" length 3

Prefix maxima:

Position left
... ...
after aaa 3
end 3

Suffix maxima:

Position right
start 3
before bbb 3
end 1

Best split occurs between the two palindromes:

3 × 3 = 9

Answer:

9

func maxProduct(s string) int64 { n := len(s) oddLen := make([]int, n) center, right := 0, 0

for i := 0; i < n; i++ {
    mirror := 2*center - i
    if i < right {
        if oddLen[mirror] < right-i {
            oddLen[i] = oddLen[mirror]
        } else {
            oddLen[i] = right - i
        }
    }
    a, b := i-oddLen[i]-1, i+oddLen[i]+1
    for a >= 0 && b < n && s[a] == s[b] {
        oddLen[i]++
        a--
        b++
    }
    if i+oddLen[i] > right {
        center, right = i, i+oddLen[i]
    }
}

leftMax := make([]int, n)
rightMax := make([]int, n)

for i := 0; i < n; i++ {
    length := 2*oddLen[i] + 1
    start := i - oddLen[i]
    end := i + oddLen[i]
    if leftMax[end] < length {
        leftMax[end] = length
    }
    if rightMax[start] < length {
        rightMax[start] = length
    }
}

for i := 1; i < n; i++ {
    if leftMax[i] < leftMax[i-1] {
        leftMax[i] = leftMax[i-1]
    }
}
for i := n - 2; i >= 0; i-- {
    if rightMax[i] < rightMax[i+1] {
        rightMax[i] = rightMax[i+1]
    }
}

var maxProd int64
for i := 0; i < n-1; i++ {
    prod := int64(leftMax[i] * rightMax[i+1])
    if prod > maxProd {
        maxProd = prod
    }
}
return maxProd

}


**Explanation:** The Go version mirrors the Python logic. We use slices to store palindrome lengths and max arrays. All arithmetic is carefully handled to prevent integer overflow by using `int64` for the result.

## Worked Examples

### Example 1: `s = "ababbb"`

| i | odd_len[i] | left_max | right_max |
| --- | --- | --- | --- |
| 0 | 0 | 1 | 1 |
| 1 | 1 | 3 | 3 |
| 2 | 0 | 3 | 3 |
| 3 | 0 | 3 | 3 |
| 4 | 1 | 3 | 3 |
| 5 | 0 | 3 | 3 |

Split between index 2 and 3: `left_max[2] = 3`, `right_max[3] = 3` → product = 9.

### Example 2: `s = "zaaaxbbby"`

Split between index 3 and 4: `left_max[3] = 3 ("aaa")`, `right_max[4] = 3 ("bbb")` → product = 9.

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n log n) | Manacher is O(n), heap sweeps are O(n log n) |
| Space | O(n) | Radii arrays, helper arrays, and heap storage |

The dominant cost comes from the sweep-line heap operations. Each palindrome center is inserted and removed once, producing `O(n log n)` total time. All auxiliary structures are linear in the length of the string.

## Test Cases

sol = Solution()

assert sol.maxProduct("ababbb") == 9 # example 1 assert sol.maxProduct("zaaaxbbby") == 9 # example 2

assert sol.maxProduct("aa") == 1 # smallest valid size assert sol.maxProduct("ab") == 1 # only single-character palindromes

assert sol.maxProduct("aaa") == 1 # length-3 palindrome blocks overlap assert sol.maxProduct("aaaaa") == 3 # "a" and "aaa"

assert sol.maxProduct("abcdef") == 1 # all single characters

assert sol.maxProduct("abacdc") == 9 # "aba" and "cdc"

assert sol.maxProduct("racecarxyzzyxaba") == 21 # large palindrome plus smaller one

assert sol.maxProduct("bbbbbbbb") == 9 # many overlapping palindromes

assert sol.maxProduct("a" * 1000) > 0 # stress test with repeated chars


### Test Summary

| Test | Why |
| --- | --- |
| `"ababbb"` | Official example |
| `"zaaaxbbby"` | Official example |
| `"aa"` | Minimum size |
| `"ab"` | Only length-1 palindromes |
| `"aaa"` | Overlap restriction |
| `"aaaaa"` | Dense palindrome structure |
| `"abcdef"` | No long palindromes |
| `"abacdc"` | Two disjoint length-3 palindromes |
| `"racecarxyzzyxaba"` | Mixed palindrome lengths |
| `"bbbbbbbb"` | Many overlapping candidates |
| `"a"*1000` | Stress behavior |

## Edge Cases

### All Characters Distinct

Consider:

"abcdef"


Every odd palindrome has length `1`. A buggy implementation might assume that a longer palindrome always exists or fail when only trivial palindromes are present. This solution initializes every position with palindrome length `1`, guaranteeing a valid answer of `1`.

### Large Overlapping Palindromes

Consider:

"aaaaaaa"


Many large palindromes overlap each other. The optimal answer is not necessarily obtained by selecting the two individually largest palindromes because they may intersect. By evaluating every split position independently, the implementation automatically enforces the non-overlapping requirement.

### Palindrome Touching a Boundary

Consider:

"abac"


The palindrome `"aba"` starts at index `0`. Algorithms that mishandle interval boundaries often lose palindromes touching the beginning or end of the string. The Manacher radius computation explicitly tracks left and right limits, so boundary palindromes are handled correctly.

### Entire String Is a Palindrome

Consider:

"racecar"


The largest palindrome spans almost the entire string. However, it cannot be paired with another non-overlapping palindrome. The prefix/suffix decomposition ensures that only palindromes fully contained on opposite sides of a split are multiplied, preventing invalid overlap.
| Time | O(n) | Manacher’s algorithm runs in O(n), and prefix/suffix arrays + final product calculation |