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, expand and count. Handle both odd and even length.
Every single character is a palindrome, so the count starts at n. Each successful expansion adds one more palindrome.
count = 0
for i in range(len(s)):
# Odd-length
l, r = i, i
while l >= 0 and r < len(s) and s[l] == s[r]:
count += 1
l -= 1; r += 1
# Even-length
l, r = i, i + 1
while l >= 0 and r < len(s) and s[l] == s[r]:
count += 1
l -= 1; r += 1
return countPractice Palindromic Substrings and similar 1-D Dynamic Programming problems with flashcards. Build pattern recognition through active recall.
Practice this problem