Problem Statement

Given a string of length (n), find the length of the longest palindromic substring where (n \le 10^5).

Brute-Force Approach

A straightforward method involves iterating through each position as a potential center and expanding outward in both directions to check for palindromes. Taking the maximum length among all centers yields the answer. However, this approach runs in (O(n^2)) time, which becomes impractical for large inputs.

Key Insight: Exploiting Symmetry

During the brute-force process, we observe significant redundancy. When a palindrome is discovered, its left and right sides mirror eachother. Rather than recomputing the right side, we can simply copy the results from the left side.

This observation leads to Manacher's algorithm, which achieves linear time complexity by maintaining two boundary variables and an auxiliary array.

Algorithm Framework

Three variables are maintained during the algorithm:

• rightBound: The rightmost index reached by any palindrome discovered so far
• center: The center index of the palindrome that extends to rightBound
• radius[i]: The maximum palindrome radius when using index i as the center

Handling Odd and Even Lengths

To treat both odd and even length palindromes uniformly, we insert a delimiter character between each pair of adjacent characters. Using # as the delimiter ensures the transformed string always has odd length:

string transformed = "@#";
for (int i = 0; i < n; ++i) {
    transformed += s[i];
    transformed += '#';
}

This preprocessing allows us to consider only odd-length palindromes in the transformed string.

Three Cases for Radius Computation

Let j denote the mirror position of i with respect to center, computed as j = 2 * center - i.

Case 1: i < rightBound and radius[j] <= rightBound - i

When i lies within the current right boundary and the mirror's radius fits entirely within the boundary, the palindrome at i mirrors the one at j. Thus, radius[i] = radius[j].

Case 2: i < rightBound and radius[j] > rightBound - i

The mirror's radius extends beyond the current boundary. Only the portion within [i, rightBound] is guaranteed to be palindromic. Therefore, radius[i] = rightBound - i.

Case 3: i >= rightBound

When i lies outside the current boundary, no prior information can be reused. The radius initializes to 1, and we must compute it through manual expansion.

Implementation

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    string input;
    cin >> n >> input;
    
    string str = "@#";
    for (char c : input) {
        str += c;
        str += '#';
    }
    
    int m = str.size();
    vector<int> radius(m, 0);
    int center = 0, rightBound = 0;
    int maxLen = 0;
    
    for (int i = 1; i < m; ++i) {
        // Determine initial radius
        if (i < rightBound) {
            int mirror = 2 * center - i;
            radius[i] = min(radius[mirror], rightBound - i);
        } else {
            radius[i] = 1;
        }
        
        // Attempt to expand beyond the initial radius
        while (str[i - radius[i]] == str[i + radius[i]]) {
            radius[i]++;
        }
        
        // Update boundaries if this palindrome extends further
        if (i + radius[i] > rightBound) {
            center = i;
            rightBound = i + radius[i];
        }
        
        // Track maximum length (subtract 1 for delimiter)
        maxLen = max(maxLen, radius[i] - 1);
    }
    
    cout << maxLen << '\n';
    return 0;
}

Complexity Analysis

The algorithm processes each character at most twice: once during initial radius determination and once during expansion. Therefore, the time complexity is (O(n)) and the space complexity is (O(n)).

The maximum value stored in radius[i] - 1 across all positions gives the length of the longest palindromic substring.