Maximum Product of the Length of Two Palindromic Substrings

HARD

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 <= 10⁵
s consists of lowercase English letters.

Approaches

Checkout 3 different approaches to solve Maximum Product of the Length of Two Palindromic Substrings. Click on different approaches to view the approach and algorithm in detail.

Brute Force with Split Point

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.

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 Analysis

Time Complexity: 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 Complexity: O(1)

Pros and Cons

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.

Code Solutions

Checking out 1 solution in different languages for Maximum Product of the Length of Two Palindromic Substrings. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Maximum Product of the Length of Two Palindromic Substrings

Patterns:

Rolling HashHash Function

Data Structures:

String