In this LeetCode challenge we’re asked to find the longest palindrome in a given string (a palindrome being a sequence of characters that is the same backwards as it is forwards, such as “bob”).
Now you might be inclined to think that the solution to this is simply to look at every character, and then move outwards until the characters no longer mirror each other. However, whilst this would work for a string like “aba”, it would not work for a string like “abba”, so we need to look for mirrored characters both by individual letter, and by letter-couple.
Solution #1: Loop, call twice, and store globally
Not a catchy title I know, but as this is my only real solution a catchy name seemed unnecessary!
In this solution, we loop through all characters in the string, and for each one, we begin checking for palindromes both on the current character and on the current character-couple. For each palindrome found, we check if it’s the new longest one, and store it if so.
This solution works great, and is pretty quick. In fact, the only way I’ve found to improve its performance is to replace the somewhat expensive string storing operations with pointer storage instead. In other words, instead of storing (and subsequently overwriting) the longest palindromes found each time, we instead store (and overwrite) pointers to the start and end of the longest palindrome. As you can imagine, once we get seriously long strings, this really starts to improve performance (at the cost of readability).
Top comments (1)
really like this solution, thanks for writing it up!