1
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ How do you get $O(n^2)$? $\endgroup$
    – Steven
    Commented May 14, 2021 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
    Commented May 14, 2021 at 13:53

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.