# Longest palindrome after swapping operation

I know that Manacher's algorithm can be used to find the longest palindromic substring of a string in linear time. But I want to find the longest palindromic substring after swapping any two indices once.

If I run a for loop twice in $$O(n^2)$$ to find all possible swaps and find the max of all formed strings I get the ans but in $$O(n^3)$$. Is there a better way like $$O(n)$$?

• How do you get $O(n^2)$? May 14 '21 at 13:41
• I think i made a mistake. It will be n^3. Manachers algo on each possible string formed after a swap. May 14 '21 at 13:53