Maximum Product of the Length of Two Palindromic Substrings
HardPrompt
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 <= 105sconsists of lowercase English letters.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach considers every possible way to split the string into two non-empty, non-overlapping substrings. For each split, it exhaustively searches for the longest odd-length palindrome in the left substring and the longest odd-length palindrome in the right substring. The product of these two lengths is a candidate for the maximum product.
Algorithm
- Initialize a variable
max_productto 0. - Iterate through all possible split points
pfrom1tos.length() - 1. - For each split point
p, the string is divided into two parts: a left parts[0...p-1]and a right parts[p...s.length()-1]. - Find the maximum length of an odd-length palindrome in the left part (
max_len_left).- To do this, iterate through every character in the left part as a potential center.
- For each center, expand outwards to find the longest palindrome and keep track of the maximum length found.
- Find the maximum length of an odd-length palindrome in the right part (
max_len_right) using the same expansion method. - If both
max_len_leftandmax_len_rightare greater than 0, calculate their product. - Update
max_product = max(max_product, max_len_left * max_len_right). - After checking all split points, return
max_product.
Walkthrough
The core idea is to iterate through every possible index p that can serve as a boundary between the two palindromic substrings. For a given p, one palindrome must lie entirely within s[0...p-1] and the other entirely within s[p...n-1].
For each such partition, we need to find the maximum possible length of an odd-length palindrome on the left side and on the right side. This is done by a helper function, findMaxOddPalindrome, which iterates through all possible centers in a given substring and expands outwards to find the longest palindrome for each center. This process is computationally expensive because for each of the n-1 splits, we perform a search that takes roughly O(p^2) for the left part and O((n-p)^2) for the right part, leading to an overall cubic time complexity.
class Solution { public long maxProduct(String s) { int n = s.length(); if (n < 2) { return 0; } long maxProd = 0; for (int i = 1; i < n; i++) { long leftMax = findMaxOddPalindrome(s, 0, i - 1); long rightMax = findMaxOddPalindrome(s, i, n - 1); if (leftMax > 0 && rightMax > 0) { maxProd = Math.max(maxProd, leftMax * rightMax); } } return maxProd; } private int findMaxOddPalindrome(String s, int start, int end) { int maxLen = 0; for (int i = start; i <= end; i++) { // Expand from center i int l = i, r = i; while (l >= start && r <= end && s.charAt(l) == s.charAt(r)) { maxLen = Math.max(maxLen, r - l + 1); l--; r++; } } // If no palindrome is found, every single character is a palindrome of length 1. return maxLen > 0 ? maxLen : (end >= start ? 1 : 0); }}Complexity
Time
O(n^3), where n is the length of the string. The outer loop runs `n` times for the split point. Inside, finding the max palindrome takes O(length^2), leading to a total of `Sum(p^2 + (n-p)^2)` for `p` from 1 to `n-1`, which is O(n^3).
Space
O(1)
Trade-offs
Pros
Simple to conceptualize and implement.
Correctly models the problem of non-intersecting substrings.
Cons
Extremely inefficient due to nested loops and repeated computations.
Will result in a 'Time Limit Exceeded' error for the given constraints.
Solutions
Solution
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; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.