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.

 

Solutions

Solution: Manacher’s Algorithm

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
const maxProduct = function (s) {
  const n = s.length;

  const manacher = str => {
    const maxExtends = Array.from({ length: n }, () => 0);
    const leftToRight = Array.from({ length: n }, () => 1);
    let center = 0;

    for (let index = 0; index < n; index++) {
      const r = center + maxExtends[center] - 1;
      const mirrorIndex = center - (index - center);
      let extend = index > r ? 1 : Math.min(maxExtends[mirrorIndex], r - index + 1);

      while (index - extend >= 0 && index + extend < n && str[index - extend] === str[index + extend]) {
        leftToRight[index + extend] = 2 * extend + 1;
        extend += 1;
      }

      maxExtends[index] = extend;

      if (index + maxExtends[index] >= r) {
        center = index;
      }
    }

    for (let index = 1; index < n; index++) {
      leftToRight[index] = Math.max(leftToRight[index], leftToRight[index - 1]);
    }

    return leftToRight;
  };

  const maxLeft = manacher(s);
  const reversed = s.split('').reverse().join('');
  const maxRight = manacher(reversed).reverse();
  let reuslt = 1;

  for (let index = 1; index < n; index++) {
    reuslt = Math.max(reuslt, maxLeft[index - 1] * maxRight[index]);
  }

  return reuslt;
};