647. Palindromic Substrings

Description

See: https://leetcode.com/problems/palindromic-substrings/

Solution

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

"""
"a"
"aa"
"ab"
"abc"
"aaa"
"abba"
"aba"
"abaca"
"abbba"
"ababa"
"""

Time complexity: O(N^2).

Space complexity: O(1)