647. Palindromic Substrings


See: https://leetcode.com/problems/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)

Last updated