Maximum product of the length of two palindromic substrings

Two Pointers String Rolling Hash Hash Function

30.9% acceptance

Mar 1, 2026

255

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_product(s: String) -> i64 {
    let s = s.as_bytes();
    let n = s.len();
    
    // Manacher's algorithm for odd-length palindromes
    let mut p = vec![0usize; n]; // p[i] = radius of longest palindrome centered at i
    let mut c = 0;
    let mut r = 0usize; // rightmost boundary (exclusive)
    for i in 0..n {
      if i < r {
        p[i] = p[2 * c - i].min(r - i - 1);
      }
      while i >= p[i] + 1 && i + p[i] + 1 < n && s[i - p[i] - 1] == s[i + p[i] + 1] {
        p[i] += 1;
      }
      if i + p[i] + 1 > r {
        c = i;
        r = i + p[i] + 1;
      }
    }
    
    // For each position, compute the longest odd palindrome ending at or before i (prefix)
    // and the longest odd palindrome starting at or after i (suffix)
    
    // prefix[i] = length of longest odd palindromic substring ending at or before index i
    let mut prefix = vec![1i64; n];
    // suffix[i] = length of longest odd palindromic substring starting at or after index i
    let mut suffix = vec![1i64; n];
    
    // For prefix: iterate centers, each center c with radius p[c] gives palindrome ending at c+p[c]
    // We want for each right endpoint, the max palindrome length
    // Use the approach: for each center, the palindrome covers [c-p[c], c+p[c]]
    // The longest palindrome ending exactly at position j is found by checking centers
    // But we need an efficient approach.
    
    // Better approach: use the fact that if there's a palindrome of length L ending at position j,
    // there's also one of length L-2 ending at j. So we can propagate.
    
    // max_reach[i] = the farthest right that a palindrome centered at i can reach = i + p[i]
    // For prefix computation:
    // We sweep left to right. We maintain the best palindrome that can extend to current position.
    // For each position j, the longest palindrome ending at j has center c where c + p[c] >= j,
    // and its length is 2*(j-c)+1. We want to maximize j-c subject to c+p[c] >= j.
    
    // Efficient approach: track the leftmost center whose palindrome still covers position j
    {
      let mut best_center = 0;
      for j in 0..n {
        // Find leftmost center whose palindrome reaches j
        while best_center + p[best_center] < j {
          best_center += 1;
        }
        // The palindrome centered at best_center reaching j has length 2*(j - best_center) + 1
        prefix[j] = (2 * (j - best_center) + 1) as i64;
        if j > 0 && prefix[j] < prefix[j - 1] {
          prefix[j] = prefix[j - 1];
        }
      }
    }
    
    {
      let mut best_center = n - 1;
      for j in (0..n).rev() {
        // Find rightmost center whose palindrome starts at or before j
        while best_center > j && best_center - p[best_center] > j {
          best_center -= 1;
        }
        suffix[j] = (2 * (best_center - j) + 1) as i64;
        if j + 1 < n && suffix[j] < suffix[j + 1] {
          suffix[j] = suffix[j + 1];
        }
      }
    }
    
    let mut ans: i64 = 1;
    for i in 0..n - 1 {
      ans = ans.max(prefix[i] * suffix[i + 1]);
    }
    ans
  }
}