LeetCode 1960: Maximum Product of the Length of Two Palindromic Substrings Solution

Master LeetCode problem 1960 (Maximum Product of the Length of Two Palindromic Substrings), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1960. Maximum Product of the Length of Two Palindromic Substrings

Hard

String Rolling Hash Hash Function

Problem Explanation

Explanation:

To solve this problem, we can use dynamic programming to find the longest palindromic substring centered at each position in the input string. Then, we iterate through all possible pairs of non-intersecting palindromic substrings with odd lengths and calculate their product. Finally, we return the maximum product found.

Find the longest palindromic substring centered at each position:
- We can use the Manacher's Algorithm to find the longest palindromic substring centered at each position in linear time complexity.
Iterate through all pairs of non-intersecting palindromic substrings with odd lengths:
- For each palindromic substring with odd length, we can extend it to the left and right as much as possible to get the maximum length.
- Then, we calculate the product of the lengths of all pairs of non-intersecting palindromic substrings with odd lengths.
Return the maximum product found.

Time Complexity:

The time complexity of this approach is O(n^2) where n is the length of the input string. This is because we iterate through all positions to find the longest palindromic substrings and then iterate through all pairs of non-intersecting palindromic substrings.

Space Complexity:

The space complexity is O(n) to store the lengths of longest palindromic substrings centered at each position.

Solution Code

class Solution {
    public long maxProduct(String s) {
        int n = s.length();
        
        int[] oddPalindromeLengths = new int[n];
        int[] evenPalindromeLengths = new int[n];
        
        for (int i = 0, l = 0, r = -1; i < n; i++) {
            int k = (i > r) ? 1 : Math.min(oddPalindromeLengths[l + r - i], r - i);
            while (i - k >= 0 && i + k < n && s.charAt(i - k) == s.charAt(i + k)) {
                k++;
            }
            oddPalindromeLengths[i] = k--;
            if (i + k > r) {
                l = i - k;
                r = i + k;
            }
        }

        // Find even length palindromes
        for (int i = 0, l = 0, r = -1; i < n; i++) {
            int k = (i > r) ? 0 : Math.min(evenPalindromeLengths[l + r - i + 1], r - i + 1);
            while (i - k - 1 >= 0 && i + k < n && s.charAt(i - k - 1) == s.charAt(i + k)) {
                k++;
            }
            evenPalindromeLengths[i] = k--;
            if (i + k > r) {
                l = i - k - 1;
                r = i + k;
            }
        }
        
        long maxProduct = 0;
        for (int i = 0; i < n - 1; i++) {
            maxProduct = Math.max((long) oddPalindromeLengths[i] * oddPalindromeLengths[i + 1], maxProduct);
            maxProduct = Math.max((long) evenPalindromeLengths[i] * evenPalindromeLengths[i + 1], maxProduct);
        }
        
        return maxProduct;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1960 (Maximum Product of the Length of Two Palindromic Substrings)?

This page provides optimized solutions for LeetCode problem 1960 (Maximum Product of the Length of Two Palindromic Substrings) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1960 (Maximum Product of the Length of Two Palindromic Substrings)?

The time complexity for LeetCode 1960 (Maximum Product of the Length of Two Palindromic Substrings) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1960 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1960 in Java, C++, or Python.

Back to LeetCode Solutions