Manacher's Algorithm

Explanation:

- **Manacher's Algorithm** is an efficient algorithm to find the **longest palindromic substring** in linear time **O(n)**.
-
- It avoids redundant checks by expanding around possible centers while using previously computed results to minimize effort.

-

• Steps:

  • Transform the input string to insert special characters (e.g., #) between each character and at the ends, so every palindrome has an odd length.
  • Use a center-expansion technique to find palindromes while maintaining the current rightmost palindrome’s boundaries.
  • Update the result if a longer palindrome is found during the process.

• Time Complexity:

  • Time complexity: O(n), where n is the length of the string.