Welcome to Subscribe On Youtube
1960. Maximum Product of the Length of Two Palindromic Substrings
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.
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. s[i...j]
denotes a substring from index i
to index j
inclusive.
Return the maximum possible product of the lengths of the two non-intersecting palindromic substrings.
A palindrome is a string that is the same forward and backward. A substring is a contiguous sequence of characters in a string.
Example 1:
Input: s = "ababbb" Output: 9 Explanation: Substrings "aba" and "bbb" are palindromes with odd length. product = 3 * 3 = 9.
Example 2:
Input: s = "zaaaxbbby" Output: 9 Explanation: Substrings "aaa" and "bbb" are palindromes with odd length. product = 3 * 3 = 9.
Constraints:
2 <= s.length <= 105
s
consists of lowercase English letters.
Solution
Use Manacher’s Algorithm. For each position in s
, find the length of the longest palindrome that has the center at the position. Then find two non-overlapping longest palindromes and return their product.
-
class Solution { public long maxProduct(String s) { int length = s.length(); int[] span = new int[length]; for (int i = 0, l = 0, r = -1; i < length; i++) { span[i] = i <= r ? Math.min(span[l + r - i], r - i + 1) : 1; while (i - span[i] >= 0 && i + span[i] < length && s.charAt(i - span[i]) == s.charAt(i + span[i])) span[i]++; if (i + span[i] - 1 > r) { l = i - span[i] + 1; r = i + span[i] - 1; } } int[] pre = new int[length]; int[] suf = new int[length]; for (int i = 0; i < length; i++) { pre[i + span[i] - 1] = Math.max(pre[i + span[i] - 1], span[i] * 2 - 1); suf[i - span[i] + 1] = Math.max(suf[i - span[i] + 1], span[i] * 2 - 1); } for (int i = 1; i < length; i++) pre[i] = Math.max(pre[i], pre[i - 1]); for (int i = length - 2; i >= 0; i--) pre[i] = Math.max(pre[i], pre[i + 1] - 2); for (int i = length - 2; i >= 0; i--) suf[i] = Math.max(suf[i], suf[i + 1]); for (int i = 1; i < length; i++) suf[i] = Math.max(suf[i], suf[i - 1] - 2); long product = 0; for (int i = 0; i < length - 1; i++) product = Math.max(product, (long) pre[i] * suf[i + 1]); return product; } }
-
class Solution { public: long long maxProduct(string s) { long long res = 0, l = 0, n = s.size(); vector<int> m(n), r(n); for (int i = 0, l = 0, r = -1; i < n; ++i) { int k = (i > r) ? 1 : min(m[l + r - i], r - i + 1); while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) k++; m[i] = k--; if (i + k > r) { l = i - k; r = i + k; } } queue<array<int, 2>> q, q1; for (int i = n - 1; i >= 0; --i) { while (!q.empty() && q.front()[0] - q.front()[1] > i - 1) q.pop(); r[i] = 1 + (q.empty() ? 0 : (q.front()[0] - i) * 2); q.push({i, m[i]}); } for (int i = 0; i < n - 1; i++) { while (!q1.empty() && q1.front()[0] + q1.front()[1] < i + 1) q1.pop(); l = max(l, 1ll + (q1.empty() ? 0 : (i - q1.front()[0]) * 2)); res = max(res, l * r[i + 1]); q1.push({i, m[i]}); } return res; } };
-
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))
-
func maxProduct(s string) int64 { n := len(s) hlen := make([]int, n) center, right := 0, 0 for i := 0; i < n; i++ { if i < right { mirror := 2*center - i if mirror >= 0 && mirror < n { hlen[i] = min(right-i, hlen[mirror]) } } for i-1-hlen[i] >= 0 && i+1+hlen[i] < n && s[i-1-hlen[i]] == s[i+1+hlen[i]] { hlen[i]++ } if i+hlen[i] > right { center = i right = i + hlen[i] } } prefix := make([]int, n) suffix := make([]int, n) for i := 0; i < n; i++ { r := i + hlen[i] if r < n { prefix[r] = max(prefix[r], 2*hlen[i]+1) } l := i - hlen[i] if l >= 0 { suffix[l] = max(suffix[l], 2*hlen[i]+1) } } for i := 1; i < n; i++ { if n-i-1 >= 0 { prefix[n-i-1] = max(prefix[n-i-1], prefix[n-i]-2) } suffix[i] = max(suffix[i], suffix[i-1]-2) } for i := 1; i < n; i++ { prefix[i] = max(prefix[i-1], prefix[i]) suffix[n-i-1] = max(suffix[n-i], suffix[n-i-1]) } var res int64 for i := 1; i < n; i++ { prod := int64(prefix[i-1]) * int64(suffix[i]) if prod > res { res = prod } } return res }