This occasionally comes up during coding interviews and is actually quite a decent way to test someone’s aptitude of moving back and forth on a string to determine if and where palindromes exist.
If we simply said: “return a boolean if a string is a palindrome”, then threw a couple tests cases at the function, we would expect the developer to loop through the first half of a string while comparing the second half, if it matched all the way to the central pivot, then “yes, the string is a palindrome”.
However, this is a bit more complex.
The problem statement
“Give a string
s, find the longest palindromic substring in
There may be multiple ways to achieve this, so coming up with a decent time and space answer is more ideal.
How do we solve this?
We start by creating a variable to remember our palindrome (which we hopefully find).
Then we loop through the input string, followed by a second loop in reverse through the same string.
At this point we check both positions to determine their match and return once we’re done.