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: 3

💡 Note: Split at position 1: left "z" has palindrome "z" (length 1), right "aba" has palindrome "aba" (length 3). Product: 1 × 3 = 3.

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

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

✓ Brute Force - Check All Pairs

⏱️ Time: O(n⁵) Space: O(1)

For every possible split point, check all palindromes before it and all palindromes after it. Calculate the product of lengths for each valid pair and return the maximum.

Optimized with Expand Around Centers

⏱️ Time: O(n³) Space: O(n²)

For each possible center, expand outward to find all odd-length palindromes. Then for each split point, track the maximum palindrome length in left and right parts.

Prefix/Suffix Maximum Arrays

⏱️ Time: O(n²) Space: O(n)

First find all palindromes, then create prefix array storing maximum palindrome length ending at or before each position, and suffix array for palindromes starting at or after each position.

Brute Force - Check All Pairs — Algorithm Steps

For each split point k
Find all odd-length palindromes before k
Find all odd-length palindromes after k
Calculate product for each pair
Return maximum product

Visualization

Tap to expand

Step-by-Step Walkthrough

Split Point

Try each position as a boundary between left and right parts

Find Palindromes

Find longest odd palindrome in each part

Calculate Product

Multiply lengths and track maximum

Code -

solution.c — C

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

bool isPalindrome(const char* str, int start, int end) {
    while (start < end) {
        if (str[start] != str[end]) {
            return false;
        }
        start++;
        end--;
    }
    return true;
}

int solution(char* s) {
    int n = strlen(s);
    int maxProduct = 0;
    
    // Try all possible split points
    for (int k = 1; k < n; k++) {
        int leftMax = 0;
        int rightMax = 0;
        
        // Find longest odd palindrome in left part [0...k-1]
        for (int i = 0; i < k; i++) {
            for (int j = i; j < k; j++) {
                int length = j - i + 1;
                if (length % 2 == 1 && isPalindrome(s, i, j)) {
                    if (length > leftMax) {
                        leftMax = length;
                    }
                }
            }
        }
        
        // Find longest odd palindrome in right part [k...n-1]
        for (int i = k; i < n; i++) {
            for (int j = i; j < n; j++) {
                int length = j - i + 1;
                if (length % 2 == 1 && isPalindrome(s, i, j)) {
                    if (length > rightMax) {
                        rightMax = 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) split points × O(n²) palindrome pairs × O(n) palindrome verification for each pair

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear 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

Maximum Product of the Length of Two Palindromic Substrings - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Pairs — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler