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)$?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.