Maximum Product of the Length of Two Palindromic Substrings

Maximum Product of the Length of Two Palindromic Substrings - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: s = "ababbb"

› Output: 9

💡 Note: The optimal split is at position 3. Left part "aba" has palindrome "aba" (length 3), right part "bbb" has palindrome "bbb" (length 3). Product: 3 × 3 = 9.

Example 2 — Single Characters

$ Input: s = "zaba"

› Output: 1

💡 Note: Split at position 1: left "z" (length 1), right "aba" has palindrome "aba" (length 3). But we can also split at position 2: left "za" has palindrome "a" (length 1), right "ba" has palindrome "a" (length 1). Best product is 1 × 3 = 3, but checking all positions gives us 1.

Example 3 — No Valid Split

$ Input: s = "aa"

› Output: 0

💡 Note: We need odd-length palindromes. "aa" has even length, so there's no way to find two non-intersecting odd-length palindromes.

Constraints

2 ≤ s.length ≤ 10⁵
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input String

Given string s = "ababbb"

Find Split

Try each position as boundary between left and right parts

Calculate Product

Find best palindromes in each part and multiply lengths

Key Takeaway

🎯 Key Insight: Use expand-around-centers to find palindromes efficiently, then precompute maximum lengths for quick split evaluation

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to find all odd-length palindromes efficiently using expand-around-centers, then use prefix/suffix arrays to quickly determine the maximum palindrome length available before and after each split point. The optimal approach runs in O(n²) time and O(n) space by precomputing maximum palindrome lengths.

Common Approaches

Approach	Time	Space	Notes
✓ Optimized with Expand Around Centers	O(n³)	O(n²)	Use expand around centers to find palindromes efficiently, then check all splits
Prefix/Suffix Maximum Arrays	O(n²)	O(n)	Precompute maximum palindrome lengths using prefix and suffix arrays
Brute Force - Check All Pairs	O(n⁵)	O(1)	Check every possible pair of non-intersecting substrings for palindromes

Optimized with Expand Around Centers — Algorithm Steps

Find all palindromes using expand around centers
For each split point k
Find max palindrome ending before k
Find max palindrome starting after k
Calculate product and update maximum

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Palindromes

Expand around each character to find all odd palindromes

Split and Search

For each split, find max palindrome in left and right parts

Calculate Product

Multiply lengths and track maximum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int left, right, length;
} Palindrome;

int solution(char* s) {
    int n = strlen(s);
    if (n < 2) return 0;
    
    // Find all odd-length palindromes
    Palindrome palindromes[10000];
    int count = 0;
    
    // Expand around each center
    for (int center = 0; center < n; center++) {
        int left = center, right = center;
        while (left >= 0 && right < n && s[left] == s[right]) {
            int length = right - left + 1;
            palindromes[count++] = (Palindrome){left, right, length};
            left--;
            right++;
        }
    }
    
    int maxProduct = 0;
    
    // Try each split point
    for (int k = 1; k < n; k++) {
        int leftMax = 0;
        int rightMax = 0;
        
        // Find max palindrome length in left part [0, k-1]
        for (int i = 0; i < count; i++) {
            if (palindromes[i].right < k) {
                if (palindromes[i].length > leftMax) {
                    leftMax = palindromes[i].length;
                }
            }
        }
        
        // Find max palindrome length in right part [k, n-1]
        for (int i = 0; i < count; i++) {
            if (palindromes[i].left >= k) {
                if (palindromes[i].length > rightMax) {
                    rightMax = palindromes[i].length;
                }
            }
        }
        
        if (leftMax > 0 && rightMax > 0) {
            int product = leftMax * rightMax;
            if (product > maxProduct) {
                maxProduct = product;
            }
        }
    }
    
    return maxProduct;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

O(n²) to find all palindromes using expand around centers + O(n²) to check all splits and find max lengths

⚠ Quadratic Growth

Space Complexity

O(n²)

Storing palindrome information for all possible substrings

⚠ Quadratic Space

8.5K Views

Medium Frequency

~35 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized with Expand Around Centers — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler