Every Palindrome, Counted — Solution & Editorial

Back to the Problem

Manacher's algorithm computes the palindrome radius at every odd and even center in O(n); the total count is the sum of all radii (each radius r contributes r palindromes centered there).

Complexity: O(|S|)

Watch out: Count reaches ~10¹² for 'aaaa...'; 64-bit.