Interview challenge · medium · string, dynamic-programming, expand-around-center
Longest Palindromic Substring
El reto
El enunciado va en inglés, igual que en el vídeo.
Given a string s, return the longest contiguous substring of s that is a palindrome (reads the same backwards). If there are several of the same length, any one is accepted.
Example
"babad" -> "bab" ("aba" is also right)
"cbbd" -> "bb"
"racecar" -> "racecar"
"a" -> "a"Idea: every palindrome has a center: a character (odd length) or the gap between two characters (even length). From each of the 2n - 1 centers, grow outwards while both ends match, and keep the longest. Time O(n^2), space O(1). (Manacher's algorithm does it in O(n), but this is the one asked for in interviews.)
La solución
# Longest Palindromic Substring - ayotl.dev
def grow(s, lo, hi):
# expand while both ends match
while lo >= 0 and hi < len(s):
if s[lo] != s[hi]:
break
lo, hi = lo - 1, hi + 1
return s[lo + 1:hi]
def longest_pal(s):
best = ""
for i in range(len(s)):
# odd center, then even center
for p in (grow(s, i, i),
grow(s, i, i + 1)):
if len(p) > len(best):
best = p
return best
for s in ["babad", "cbbd", "racecar", "a"]:
print(s, "->", longest_pal(s))
$ python3 longest_palindromic_substring.py
babad -> bab
cbbd -> bb
racecar -> racecar
a -> a