#5 - Longest Palindromic Substring - Leetcode

Finding the longest palindromic substring is a classic algorithm problem that often shows up in interviews. In this article, we’ll explore different approaches, their time complexities, and why the fastest known solution, Manacher’s Algorithm is still O(n) despite what appears to be nested loops.

✅ Problem Statement

Given a string s, return the longest substring which is a palindrome.

Example:

Input: "babad"
Output: "bab" // or "aba"        

🧠 What is a Palindrome?

A palindrome is a string that reads the same backward and forward, like "racecar" or "abba".

🛠️ Approach 1: Brute Force

Try all possible substrings, check each one to see if it’s a palindrome, and keep track of the longest.

• Time Complexity: O(n³)
• Space Complexity: O(1)
• Status: ❌ Too slow for large strings

⚡️ Approach 2: Expand Around Center (Most Practical)

This clever trick involves expanding around each possible palindrome "center" in the string.

• Time Complexity: O(n²)
• Space Complexity: O(1)
• Status: ✅ Great for real-world use and interviews

🚀 Approach 3: Manacher’s Algorithm (O(n) Time)

Manacher's Algorithm is the fastest known algorithm for this problem. It preprocesses the input string by inserting separators (#) to treat even and odd length palindromes uniformly.

🔍 Why Manacher’s is O(n) Despite Nested Loops

It looks like we have a for loop with a while inside. So why isn’t it O(n²)?

✅ Because:

• Each expansion (inside while) increases the palindrome radius at most once per character.
• The total number of such expansions across all iterations is bounded by O(n).

This is a classic example where amortized analysis reveals a linear runtime.

🏁 Final Thoughts

• Use Expand Around Center in interviews and production—it’s clean, fast, and intuitive.
• Use Manacher’s Algorithm if you need absolute speed or want to flex algorithmic muscle.
• Understand the trade-offs and pick the right tool for the job.