📌 Description

Manacher's algorithm finds all palindromic substrings in linear time. It’s especially useful for solving problems involving the longest palindromic substring or counting palindromes in a string.

---

💡 Key Idea

• ⭕ Insert # between all characters and at boundaries to handle even/odd palindromes uniformly.
• ⭕ Use the mirror property of palindromes to reduce redundant checks.
• ⭕ Expand around centers and maintain the rightmost boundary of known palindromes.

Info

Given a string S, the task is to find the longest substring which is a palindrome. If there are multiple answers, then return the first appearing substring

Examples:

• Input: forgeeksskeegfor
• Output: geeksskeeg

# Info & Summary

• Date: 2025-03-22
• Completion Status: A ✅ / B ✅ / C ✅ / D ✅ / E ❌ / F ❌ / G ❌
• Problem Type:

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
E	Bipartite graph	BFS	⭐🔥🛠️
F	Palindrome	Manacher's Algorithm	⭐🔥🛠️
G	Graph/Bipartite Graph	Simulation	🌀