This problem follows the Expand Around Center pattern, commonly found in the 1-D Dynamic Programming category. Recognizing this pattern is key to solving it efficiently in an interview setting.
For each center (and between-centers), expand outward while palindrome holds.
Expanding from centers is simpler than the DP table approach — there are only 2n-1 centers (n odd + n-1 even), each expansion is O(n) worst case.
result = ""
for i in range(len(s)):
# Odd-length palindrome
l, r = i, i
while l >= 0 and r < len(s) and s[l] == s[r]:
if r - l + 1 > len(result):
result = s[l:r+1]
l -= 1; r += 1
# Even-length palindrome
l, r = i, i + 1
while l >= 0 and r < len(s) and s[l] == s[r]:
if r - l + 1 > len(result):
result = s[l:r+1]
l -= 1; r += 1
return resultPractice Longest Palindromic Substring and similar 1-D Dynamic Programming problems with flashcards. Build pattern recognition through active recall.
Practice this problem