Maximum Product of the Length of Two Palindromic Substrings — LeetCode 1960 Python Solution
- Problem
- #1960
- Pattern
- Hash Map
- Reading time
- 6 min
- Source
- leetcode.com
The problem
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. More formally, you want to choose four integers i, j, k, l such that 0 <= i <= j < k <= l < s.length and both the substrings s[i...j] and s[k...l] are palindromes and have odd lengths.
Example
- Input
- s = "ababbb"
- Output
- 9
- Explanation
- Substrings "aba" and "bbb" are palindromes with odd length. product = 3 * 3 = 9.
Python solution
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))Complexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(1) to O(n) auxiliary |
Pattern: Hash Map
Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 1960. Maximum Product of the Length of Two Palindromic Substrings is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.
The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1960. Maximum Product of the Length of Two Palindromic Substrings?
- LeetCode 1960. Maximum Product of the Length of Two Palindromic Substrings is rated Hard on LeetCode.
- What topics does LeetCode 1960. Maximum Product of the Length of Two Palindromic Substrings cover?
- LeetCode 1960. Maximum Product of the Length of Two Palindromic Substrings is tagged String, Hash Function and Rolling Hash on LeetCode.