Manacher's Algorithm
Learn Manacher's Algorithm (Strings, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Finding the Longest Palindromic Substring in O(n) Expand-around-center finds the longest palindromic substring in O(n²). Manacher's Algorithm does the same job in O(n) by REUSING previously computed palindrome radii, the same "don't redo known work" idea behind KMP and the Z Algorithm. The trick that avoids handling odd/even length palindromes separately: insert a separator character (like # ) between every character (and at both ends), so every palindrome in the transformed string has ODD length.