Maximum Product of the Length of Two Palindromic Substrings

Hard

#1787Time: 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)

Patterns

Rolling Hash Hash Function

Data structures

String

Prompt

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 <= 10⁵
s consists 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_product to 0.
Iterate through all possible split points p from 1 to s.length() - 1.
For each split point p, the string is divided into two parts: a left part s[0...p-1] and a right part s[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_left and max_len_right are 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.

1class Solution {2    public long maxProduct(String s) {3        int n = s.length();4        if (n < 2) {5            return 0;6        }7        long maxProd = 0;8 9        for (int i = 1; i < n; i++) {10            long leftMax = findMaxOddPalindrome(s, 0, i - 1);11            long rightMax = findMaxOddPalindrome(s, i, n - 1);12            if (leftMax > 0 && rightMax > 0) {13                maxProd = Math.max(maxProd, leftMax * rightMax);14            }15        }16        return maxProd;17    }18 19    private int findMaxOddPalindrome(String s, int start, int end) {20        int maxLen = 0;21        for (int i = start; i <= end; i++) {22            // Expand from center i23            int l = i, r = i;24            while (l >= start && r <= end && s.charAt(l) == s.charAt(r)) {25                maxLen = Math.max(maxLen, r - l + 1);26                l--;27                r++;28            }29        }30        // If no palindrome is found, every single character is a palindrome of length 1.31        return maxLen > 0 ? maxLen : (end >= start ? 1 : 0);32    }33}

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.

This approach improves upon the brute-force method by avoiding redundant calculations. Instead of re-calculating the longest palindrome for every possible substring split, we first precompute the lengths of all odd-length palindromes centered at every character in the string. This is done using the 'expand from center' technique. With this information, we can then efficiently build two arrays: one for the maximum palindrome length in any prefix s[0...i] and another for any suffix s[i...n-1]. Finally, we iterate through all split points and use our precomputed arrays to find the maximum product in linear time.

Algorithm

Step 1: Precompute Palindrome Radii. Create an array radii of size n. For each index i from 0 to n-1, calculate the radius of the longest odd-length palindrome centered at i by expanding outwards. Store this in radii[i]. This step takes O(n^2).
Step 2: Compute Prefix Maximums. Create an array left_max of size n. left_max[i] will store the maximum length of an odd-length palindrome contained entirely in the prefix s[0...i]. This can be computed in O(n) using the radii array.
Step 3: Compute Suffix Maximums. Create an array right_max of size n. right_max[i] will store the maximum length of an odd-length palindrome contained entirely in the suffix s[i...n-1]. This can also be computed in O(n) using the radii array.
Step 4: Calculate Maximum Product. Iterate from i = 0 to n-2. For each i, consider the split between i and i+1. The maximum product for this split is left_max[i] * right_max[i+1]. Keep track of the overall maximum product found.
Step 5: Return the final maximum product.

Walkthrough

The main bottleneck in the previous approach was the repeated O(n^2) search for palindromes. We can optimize this by doing the search just once.

Precomputation: We create an array, say radii, of the same size as the string. radii[i] will store the radius of the longest odd-length palindrome centered at s[i]. We can populate this array by iterating through each index i and expanding outwards (l=i-1, r=i+1) as long as s[l] == s[r]. This whole precomputation step takes O(n^2) time.
DP Arrays: We then use this radii array to build left_max and right_max arrays.
- left_max[i] stores the maximum length of a palindrome in s[0...i]. It can be computed as left_max[i] = max(left_max[i-1], max length of any palindrome ending at i).
- right_max[i] stores the maximum length of a palindrome in s[i...n-1]. It can be computed as right_max[i] = max(right_max[i+1], max length of any palindrome starting at i).
Final Calculation: With left_max and right_max arrays ready, we can find the answer by iterating through all n-1 split points. For a split between i and i+1, the answer is left_max[i] * right_max[i+1]. We take the maximum over all i.

1class Solution {2    public long maxProduct(String s) {3        int n = s.length();4        if (n < 2) return 0;5 6        // Step 1: Precompute radii for all odd-length palindromes (O(n^2))7        int[] radii = new int[n];8        for (int i = 0; i < n; i++) {9            int l = i, r = i;10            while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {11                radii[i] = r - i;12                l--;13                r++;14            }15        }16 17        // Step 2 & 3: Compute left_max and right_max arrays18        int[] left_max = new int[n];19        int[] right_max = new int[n];20        Arrays.fill(left_max, 1);21        Arrays.fill(right_max, 1);22 23        for (int i = 0; i < n; i++) {24            int len = 2 * radii[i] + 1;25            left_max[i + radii[i]] = Math.max(left_max[i + radii[i]], len);26            right_max[i - radii[i]] = Math.max(right_max[i - radii[i]], len);27        }28 29        // Create prefix and suffix max arrays30        for (int i = 1; i < n; i++) {31            left_max[i] = Math.max(left_max[i], left_max[i - 1]);32        }33        for (int i = n - 2; i >= 0; i--) {34            right_max[i] = Math.max(right_max[i], right_max[i + 1]);35        }36 37        // Step 4: Calculate max product38        long maxProd = 0;39        for (int i = 0; i < n - 1; i++) {40            maxProd = Math.max(maxProd, (long)left_max[i] * right_max[i + 1]);41        }42 43        return maxProd;44    }45}

Complexity

Time

O(n^2), where n is the length of the string. The precomputation of palindrome radii using 'expand from center' for all centers dominates the runtime.

Space

O(n) for storing the `radii`, `left_max`, and `right_max` arrays.

Trade-offs

Pros

Much more efficient than the pure brute-force approach.
Introduces the powerful idea of precomputation and dynamic programming.
The logic for combining results is efficient (O(n)).

Cons

The O(n^2) precomputation step is the bottleneck.
This approach is too slow for the given constraints (n <= 10^5) and will time out.

This is the most optimal approach, achieving linear time complexity. It builds upon the previous dynamic programming idea but replaces the O(n^2) 'expand from center' precomputation with the highly efficient Manacher's algorithm. Manacher's algorithm can find the lengths of all palindromes centered at each position in O(n) time. Once we have these lengths, the rest of the logic—building the prefix-max and suffix-max length arrays and then combining the results—remains the same and also runs in O(n), leading to an overall linear time solution.

Algorithm

Step 1: Compute Palindrome Radii with Manacher's Algorithm. Use a simplified version of Manacher's algorithm to find the radius of the longest odd-length palindrome centered at each index i. This computes a radii array of size n in O(n) time.
Step 2: Populate Max Lengths at End/Start Points. Initialize two arrays, left_max and right_max, of size n with 1s. Iterate from i = 0 to n-1. For each center i, find its palindrome's length len = 2*radii[i]+1, start index s = i-radii[i], and end index e = i+radii[i]. Update left_max[e] = max(left_max[e], len) and right_max[s] = max(right_max[s], len).
Step 3: Compute Prefix and Suffix Maximums.
- Perform a prefix-max scan on left_max: for i from 1 to n-1, left_max[i] = max(left_max[i], left_max[i-1]). Now, left_max[i] stores the max palindrome length in s[0...i].
- Perform a suffix-max scan on right_max: for i from n-2 down to 0, right_max[i] = max(right_max[i], right_max[i+1]). Now, right_max[i] stores the max palindrome length in s[i...n-1].
Step 4: Calculate Final Maximum Product. Initialize max_product = 0. Iterate from i = 0 to n-2 and update max_product = max(max_product, (long)left_max[i] * right_max[i+1]).
Step 5: Return max_product.

Walkthrough

The key to achieving a linear time solution is to optimize the palindrome discovery step. Manacher's algorithm is perfect for this. A simplified version tailored for odd-length palindromes can determine the radius of the longest palindrome centered at each character s[i] in O(n) time.

Algorithm Steps:

Manacher's for Odd Palindromes: We compute an array d where d[i] is the radius of the longest odd-length palindrome centered at i. This is done by intelligently reusing information from previously found palindromes to avoid redundant character comparisons.
DP Arrays Construction: We create two arrays, left and right, of size n.
- left[i] will store the max length of a palindrome ending at or before index i.
- right[i] will store the max length of a palindrome starting at or after index i. We first populate these arrays at specific indices. For a palindrome centered at c with radius r, its length is 2*r+1. It starts at c-r and ends at c+r. So we set right[c-r] = max(right[c-r], 2*r+1) and left[c+r] = max(left[c+r], 2*r+1). After iterating through all centers, we perform a prefix-max scan on left and a suffix-max scan on right to fill in the remaining values.
Combine and Conquer: Finally, we iterate through all possible split points i from 0 to n-2. The two non-intersecting palindromes are chosen from s[0...i] and s[i+1...n-1]. The maximum product for this split is left[i] * right[i+1]. We find the maximum product over all possible splits.

1class Solution {2    public long maxProduct(String s) {3        int n = s.length();4        if (n < 2) {5            return 0;6        }7 8        // Step 1: Manacher's algorithm for odd length palindromes -> O(n)9        int[] d = new int[n]; // d[i] = radius of palindrome centered at i10        int l = 0, r = -1; // [l, r] is the rightmost palindrome found so far11        for (int i = 0; i < n; i++) {12            int k = (i > r) ? 1 : Math.min(d[l + r - i], r - i + 1);13            while (i - k >= 0 && i + k < n && s.charAt(i - k) == s.charAt(i + k)) {14                k++;15            }16            d[i] = k - 1;17            if (i + d[i] > r) {18                l = i - d[i];19                r = i + d[i];20            }21        }22 23        // Step 2 & 3: Compute left and right max arrays -> O(n)24        int[] left = new int[n];25        int[] right = new int[n];26        Arrays.fill(left, 1);27        Arrays.fill(right, 1);28 29        for (int i = 0; i < n; i++) {30            int len = 2 * d[i] + 1;31            left[i + d[i]] = Math.max(left[i + d[i]], len);32            right[i - d[i]] = Math.max(right[i - d[i]], len);33        }34 35        for (int i = 1; i < n; i++) {36            left[i] = Math.max(left[i], left[i - 1]);37        }38        for (int i = n - 2; i >= 0; i--) {39            right[i] = Math.max(right[i], right[i + 1]);40        }41 42        // Step 4: Calculate max product -> O(n)43        long maxProd = 0;44        for (int i = 0; i < n - 1; i++) {45            maxProd = Math.max(maxProd, (long)left[i] * right[i + 1]);46        }47 48        return maxProd;49    }50}

Complexity

Time

O(n), where n is the length of the string. Each step (Manacher's, DP array construction, final product calculation) takes linear time.

Space

O(n) to store the radii array from Manacher's algorithm and the two DP arrays (`left` and `right`).

Trade-offs

Pros

Optimal time complexity of O(n), making it very fast for large inputs.
Efficiently solves the problem by combining a powerful algorithm (Manacher's) with dynamic programming.

Cons

The implementation is more complex due to Manacher's algorithm.
Requires careful handling of indices and array updates.

Solutions

Solution

1class Solution {2public3  long maxProduct(String s) {4    int length = s.length();5    int[] span = new int[length];6    for (int i = 0, l = 0, r = -1; i < length; i++) {7      span[i] = i <= r ? Math.min(span[l + r - i], r - i + 1) : 1;8      while (i - span[i] >= 0 && i + span[i] < length &&9             s.charAt(i - span[i]) == s.charAt(i + span[i]))10        span[i]++;11      if (i + span[i] - 1 > r) {12        l = i - span[i] + 1;13        r = i + span[i] - 1;14      }15    }16    int[] pre = new int[length];17    int[] suf = new int[length];18    for (int i = 0; i < length; i++) {19      pre[i + span[i] - 1] = Math.max(pre[i + span[i] - 1], span[i] * 2 - 1);20      suf[i - span[i] + 1] = Math.max(suf[i - span[i] + 1], span[i] * 2 - 1);21    }22    for (int i = 1; i < length; i++)23      pre[i] = Math.max(pre[i], pre[i - 1]);24    for (int i = length - 2; i >= 0; i--)25      pre[i] = Math.max(pre[i], pre[i + 1] - 2);26    for (int i = length - 2; i >= 0; i--)27      suf[i] = Math.max(suf[i], suf[i + 1]);28    for (int i = 1; i < length; i++)29      suf[i] = Math.max(suf[i], suf[i - 1] - 2);30    long product = 0;31    for (int i = 0; i < length - 1; i++)32      product = Math.max(product, (long)pre[i] * suf[i + 1]);33    return product;34  }35}

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.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  long maxProduct(String s) {4    int length = s.length();5    int[] span = new int[length];6    for (int i = 0, l = 0, r = -1; i < length; i++) {7      span[i] = i <= r ? Math.min(span[l + r - i], r - i + 1) : 1;8      while (i - span[i] >= 0 && i + span[i] < length &&9             s.charAt(i - span[i]) == s.charAt(i + span[i]))10        span[i]++;11      if (i + span[i] - 1 > r) {12        l = i - span[i] + 1;13        r = i + span[i] - 1;14      }15    }16    int[] pre = new int[length];17    int[] suf = new int[length];18    for (int i = 0; i < length; i++) {19      pre[i + span[i] - 1] = Math.max(pre[i + span[i] - 1], span[i] * 2 - 1);20      suf[i - span[i] + 1] = Math.max(suf[i - span[i] + 1], span[i] * 2 - 1);21    }22    for (int i = 1; i < length; i++)23      pre[i] = Math.max(pre[i], pre[i - 1]);24    for (int i = length - 2; i >= 0; i--)25      pre[i] = Math.max(pre[i], pre[i + 1] - 2);26    for (int i = length - 2; i >= 0; i--)27      suf[i] = Math.max(suf[i], suf[i + 1]);28    for (int i = 1; i < length; i++)29      suf[i] = Math.max(suf[i], suf[i - 1] - 2);30    long product = 0;31    for (int i = 0; i < length - 1; i++)32      product = Math.max(product, (long)pre[i] * suf[i + 1]);33    return product;34  }35}

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.