Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1960. Maximum Product of the Length of Two Palindromic Substrings - Leetcode Solution

Code Implementation

class Solution:
    def maxProduct(self, s: str) -> int:
        n = len(s)
        # Manacher's algorithm to find all palindromic substrings
        def manacher(s):
            A = '@#' + '#'.join(s) + '#$'
            Z = [0] * len(A)
            center = right = 0
            for i in range(1, len(A)-1):
                if i < right:
                    Z[i] = min(right - i, Z[2*center - i])
                while A[i + Z[i] + 1] == A[i - Z[i] - 1]:
                    Z[i] += 1
                if i + Z[i] > right:
                    center, right = i, i + Z[i]
            return Z

        Z = manacher(s)
        n = len(s)
        # For each position, the longest palindrome ending at or before i from the left
        left = [0] * n
        # For each position, the longest palindrome starting at or after i from the right
        right = [0] * n

        # Fill left
        for i in range(n):
            # odd-length
            l = i - Z[2 + 2*i] + 1
            r = i + Z[2 + 2*i] - 1
            if l >= 0 and r < n:
                left[r] = max(left[r], r - l + 1)
            # even-length
            l = i - Z[3 + 2*i] + 1
            r = i + Z[3 + 2*i]
            if l >= 0 and r-1 < n:
                left[r-1] = max(left[r-1], r - l)

        for i in range(1, n):
            left[i] = max(left[i], left[i-1])

        # Fill right
        for i in range(n-1, -1, -1):
            # odd-length
            l = i - Z[2 + 2*i] + 1
            r = i + Z[2 + 2*i] - 1
            if l >= 0 and r < n:
                right[l] = max(right[l], r - l + 1)
            # even-length
            l = i - Z[3 + 2*i] + 1
            r = i + Z[3 + 2*i]
            if l >= 0 and r-1 < n:
                right[l] = max(right[l], r - l)

        for i in range(n-2, -1, -1):
            right[i] = max(right[i], right[i+1])

        ans = 0
        for i in range(n-1):
            ans = max(ans, left[i]*right[i+1])
        return ans
      
class Solution {
public:
    int maxProduct(string s) {
        int n = s.size();
        // Manacher's algorithm
        string t = "@#";
        for (char c : s) {
            t += c;
            t += '#';
        }
        t += '$';
        int m = t.size();
        vector<int> Z(m, 0);
        int center = 0, right = 0;
        for (int i = 1; i < m - 1; ++i) {
            if (i < right)
                Z[i] = min(right - i, Z[2*center - i]);
            while (t[i + Z[i] + 1] == t[i - Z[i] - 1])
                ++Z[i];
            if (i + Z[i] > right) {
                center = i;
                right = i + Z[i];
            }
        }
        vector<int> left(n, 0), rightArr(n, 0);
        // Fill left
        for (int i = 0; i < n; ++i) {
            // odd-length
            int l = i - Z[2 + 2*i] + 1;
            int r = i + Z[2 + 2*i] - 1;
            if (l >= 0 && r < n)
                left[r] = max(left[r], r - l + 1);
            // even-length
            l = i - Z[3 + 2*i] + 1;
            r = i + Z[3 + 2*i];
            if (l >= 0 && r-1 < n)
                left[r-1] = max(left[r-1], r - l);
        }
        for (int i = 1; i < n; ++i)
            left[i] = max(left[i], left[i-1]);
        // Fill right
        for (int i = n-1; i >= 0; --i) {
            // odd-length
            int l = i - Z[2 + 2*i] + 1;
            int r = i + Z[2 + 2*i] - 1;
            if (l >= 0 && r < n)
                rightArr[l] = max(rightArr[l], r - l + 1);
            // even-length
            l = i - Z[3 + 2*i] + 1;
            r = i + Z[3 + 2*i];
            if (l >= 0 && r-1 < n)
                rightArr[l] = max(rightArr[l], r - l);
        }
        for (int i = n-2; i >= 0; --i)
            rightArr[i] = max(rightArr[i], rightArr[i+1]);
        int ans = 0;
        for (int i = 0; i < n-1; ++i)
            ans = max(ans, left[i]*rightArr[i+1]);
        return ans;
    }
};
      
class Solution {
    public int maxProduct(String s) {
        int n = s.length();
        // Manacher's algorithm
        StringBuilder t = new StringBuilder("@#");
        for (char c : s.toCharArray()) {
            t.append(c);
            t.append('#');
        }
        t.append('$');
        int m = t.length();
        int[] Z = new int[m];
        int center = 0, right = 0;
        for (int i = 1; i < m - 1; ++i) {
            if (i < right)
                Z[i] = Math.min(right - i, Z[2*center - i]);
            while (t.charAt(i + Z[i] + 1) == t.charAt(i - Z[i] - 1))
                ++Z[i];
            if (i + Z[i] > right) {
                center = i;
                right = i + Z[i];
            }
        }
        int[] left = new int[n];
        int[] rightArr = new int[n];
        // Fill left
        for (int i = 0; i < n; ++i) {
            // odd-length
            int l = i - Z[2 + 2*i] + 1;
            int r = i + Z[2 + 2*i] - 1;
            if (l >= 0 && r < n)
                left[r] = Math.max(left[r], r - l + 1);
            // even-length
            l = i - Z[3 + 2*i] + 1;
            r = i + Z[3 + 2*i];
            if (l >= 0 && r-1 < n)
                left[r-1] = Math.max(left[r-1], r - l);
        }
        for (int i = 1; i < n; ++i)
            left[i] = Math.max(left[i], left[i-1]);
        // Fill right
        for (int i = n-1; i >= 0; --i) {
            // odd-length
            int l = i - Z[2 + 2*i] + 1;
            int r = i + Z[2 + 2*i] - 1;
            if (l >= 0 && r < n)
                rightArr[l] = Math.max(rightArr[l], r - l + 1);
            // even-length
            l = i - Z[3 + 2*i] + 1;
            r = i + Z[3 + 2*i];
            if (l >= 0 && r-1 < n)
                rightArr[l] = Math.max(rightArr[l], r - l);
        }
        for (int i = n-2; i >= 0; --i)
            rightArr[i] = Math.max(rightArr[i], rightArr[i+1]);
        int ans = 0;
        for (int i = 0; i < n-1; ++i)
            ans = Math.max(ans, left[i]*rightArr[i+1]);
        return ans;
    }
}
      
var maxProduct = function(s) {
    const n = s.length;
    // Manacher's algorithm
    let t = '@#' + s.split('').join('#') + '#$';
    const Z = Array(t.length).fill(0);
    let center = 0, right = 0;
    for (let i = 1; i < t.length - 1; ++i) {
        if (i < right)
            Z[i] = Math.min(right - i, Z[2*center - i]);
        while (t[i + Z[i] + 1] === t[i - Z[i] - 1])
            ++Z[i];
        if (i + Z[i] > right) {
            center = i;
            right = i + Z[i];
        }
    }
    const left = Array(n).fill(0), rightArr = Array(n).fill(0);
    // Fill left
    for (let i = 0; i < n; ++i) {
        // odd-length
        let l = i - Z[2 + 2*i] + 1;
        let r = i + Z[2 + 2*i] - 1;
        if (l >= 0 && r < n)
            left[r] = Math.max(left[r], r - l + 1);
        // even-length
        l = i - Z[3 + 2*i] + 1;
        r = i + Z[3 + 2*i];
        if (l >= 0 && r-1 < n)
            left[r-1] = Math.max(left[r-1], r - l);
    }
    for (let i = 1; i < n; ++i)
        left[i] = Math.max(left[i], left[i-1]);
    // Fill right
    for (let i = n-1; i >= 0; --i) {
        // odd-length
        let l = i - Z[2 + 2*i] + 1;
        let r = i + Z[2 + 2*i] - 1;
        if (l >= 0 && r < n)
            rightArr[l] = Math.max(rightArr[l], r - l + 1);
        // even-length
        l = i - Z[3 + 2*i] + 1;
        r = i + Z[3 + 2*i];
        if (l >= 0 && r-1 < n)
            rightArr[l] = Math.max(rightArr[l], r - l);
    }
    for (let i = n-2; i >= 0; --i)
        rightArr[i] = Math.max(rightArr[i], rightArr[i+1]);
    let ans = 0;
    for (let i = 0; i < n-1; ++i)
        ans = Math.max(ans, left[i]*rightArr[i+1]);
    return ans;
};

Problem Description

Given a string s, you are to split it into two non-empty parts at any position. For each part, find a palindromic substring (a substring that reads the same forwards and backwards) that is fully contained within that part. The substrings for the left and right parts must not overlap. Your task is to maximize the product of the lengths of these two palindromic substrings.

  • You must choose the split point and the palindromic substrings so that the product is as large as possible.
  • Each palindromic substring must be contained entirely within its respective part (left or right).
  • The two palindromic substrings must not overlap (since they are in non-overlapping parts).
  • The input string s consists only of lowercase English letters.
  • Return the maximum possible product of the lengths of the two palindromic substrings.

Thought Process

At first, the brute-force approach is to try every possible split of the string, and for each side, try every possible palindromic substring. This is highly inefficient because for a string of length n, there are O(n) split points and O(n^2) possible substrings per side.

Instead, we realize that for each split, what matters is the longest palindromic substring ending at or before the split point on the left, and the longest palindromic substring starting at or after the split point on the right. If we can efficiently find, for each position, the longest palindrome covering that point (either as a left or right endpoint), we can compute the answer in linear time.

This leads us to use Manacher's algorithm to precompute, for every center, the maximum radius of a palindrome centered there. We then process this information into arrays that, for each position, store the maximum palindrome length ending at or before that position (for the left side) and starting at or after that position (for the right side).

Solution Approach

  • 1. Use Manacher's Algorithm:
    • Manacher's algorithm efficiently finds all palindromic substrings in O(n) time.
    • It provides, for each possible center, the radius (half-length) of the largest palindrome centered there.
  • 2. Build Left and Right Arrays:
    • Create two arrays, left[] and right[], each of length n.
    • left[i] will be the length of the longest palindrome ending at or before index i.
    • right[i] will be the length of the longest palindrome starting at or after index i.
  • 3. Populate the Arrays:
    • For each palindrome found by Manacher's algorithm, update left[r] and right[l] with the length of the palindrome, where l and r are the start and end indices.
    • Propagate the maximum values forward in left[] and backward in right[] so that each position reflects the best possible palindrome up to that point.
  • 4. Compute the Maximum Product:
    • For each possible split point i (from 0 to n-2), multiply left[i] and right[i+1].
    • Keep track of the maximum product found.
  • 5. Return the Maximum Product:
    • Return the largest product found across all split points.

This approach ensures that we only consider the best possible palindromic substrings for each side of every split, and does so efficiently.

Example Walkthrough

Let's walk through the process with an example: s = "ababbb"

  1. Step 1: Find all palindromic substrings using Manacher's algorithm.
    • Palindromes: "a", "b", "aba", "bab", "bb", "bbb", etc.
  2. Step 2: Build left[] and right[] arrays.
    • For each position, record the longest palindrome ending at or before (for left), or starting at or after (for right).
    • For example, left[2] (for "aba") is 3, right[3] (for "bbb") is 3.
  3. Step 3: Try all split points:
    • Split after index 2: left = "aba", right = "bbb"
    • Longest palindrome in left: "aba" (length 3), in right: "bbb" (length 3)
    • Product = 3 * 3 = 9
  4. Step 4: Check all split points and keep the maximum product.
    • Other splits may have smaller products.
    • So, the answer is 9.

Time and Space Complexity

  • Brute-force Approach:
    • Time: O(n^4) (for each split, check all substrings on both sides for palindromicity)
    • Space: O(1) extra
  • Optimized Approach (Manacher's Algorithm):
    • Time: O(n) for Manacher's algorithm, O(n) for building left and right arrays, O(n) for final scan, so overall O(n).
    • Space: O(n) for the arrays used.

The optimized approach is highly efficient and suitable even for large strings.

Summary

The key to solving the Maximum Product of the Length of Two Palindromic Substrings problem efficiently is recognizing that the optimal solution for each split only depends on the best palindrome on each side. By using Manacher's algorithm, we can precompute the best palindromic substrings for all possible positions in linear time. This enables us to try every split point and compute the result efficiently.

The strategy is elegant because it transforms a seemingly complex problem into a series of simple array lookups and multiplications, all built on top of a powerful string algorithm.