647. Palindromic Substrings



This problem is similar to question 5 - "Longest Palindromic Substring". It uses the same expand around the center technique as that question to solve the problem.
Here, we need to find the number of substrings that are palindromic. Instead of iterating over each substring, we can use "expand around the center". So at each character, we decrement/increment the left and right pointers and check if the values are equal or not.
class Solution:
def expand_around_center(self, s: str, left: int, right: int) -> int:
count = 0
while left >= 0 and right < len(s) and s[left] == s[right]:
count += 1
left -= 1
right += 1
return count
def countSubstrings(self, s: str) -> int:
if len(s) == 1:
return 1
count = 0
for index in range(len(s)):
# we need to consider the two cases:
# i. odd length substrings where the mid char is one letter (i.e. "aba")
# ii. even length substrings where there are two mid characters (i.e. "abba")
count += self.expand_around_center(s, index, index)
count += self.expand_around_center(s, index, index + 1)
return count
Time complexity: O(N^2).
Space complexity: O(1)