Leetcode 5. Longest Palindromic Substring (Difficulty: medium)



Given a string s, return the longest palindromic substring in s

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

My solution:

# Cases where the whole string is a palindrome
if s == s[::-1]:
   return s
# Cases with palindromic substrings res = '' for i in range(len(s)): for l,r in zip([i,i], [i,i+1]): while 0 <= l and r <= len(s) - 1 and s[l] == s[r]: if (r - l + 1) > len(res): res = s[l : r + 1] l -= 1 r += 1 return res


It's easier to derive the code by the following observations. Every palindrome has a middle point where the two coinciding sides can be defined. We then treat each character as that possible middle point. There are two classes of middle points: those that have no character ("") and those having one ("x") which in fact correspond to those substrings with an even or odd number of characters, respectively. These two cases are represented by [i,i] and [i,i+1]. We move with equal size steps to both sides of the mid-point and start looking for the case where they are not equal. This allows to measure the size of each possibility. For last, we add memory and only update its value whenever the size of the palindrome is larger than the previous one.

The first part of the code corresponds to those scenarios where the whole string is the palindrome. It's curious to realize that most of the time consuming cases in Leetcode get actually solved by this part.