What are the main approaches to finding the longest palindromic substring, and how do they compare?
There are three main ways, and they differ mostly in how much work they do and how much memory they need.
The first way is to check every possible substring. You take each pair of end points and test whether the text between them is a palindrome. That is O of n cubed for the time, because there are n squared substrings and each one takes up to n to check. It is the version to write first, because it is the easiest to see, and it is far too slow for anything but a small text.
The second way is to expand outwards from every possible centre. A palindrome is the same forwards and backwards, so it has a centre, and the centre is either a single character or a gap between two characters. You start at each centre and keep going outwards while the two characters match. That is O of n squared for the time and O of 1 for the space.
The third way is Manacher's algorithm, which is O of n for the time and O of n for the space. It is much harder to write and it is rarely worth writing by hand.
the approach the time the space how hard
--------------------- ---------- ---------- -------------
check every substring O(n^3) O(1) easy
expand around centres O(n^2) O(1) medium
Manacher's algorithm O(n) O(n) hard
So in an interview the second one is the answer, because it is fast enough for real inputs and short enough to write in a few minutes.
The next two questions in this topic show the code and the simplest version of the palindrome check.