Problem Statement in English

You’re given a string s. Your task is to count the number of palindromic substrings in s.

Approach

This problem is a slight variation of another one that I’ve covered.

Solution in Python


class Solution:
    def countSubstrings(self, s: str) -> int:
        ans = 0
        # odd
        for i in range(len(s)):
            l, r = i, i

            while l >= 0 and r < len(s) and s[l] == s[r]:
                ans += 1
                l -= 1
                r += 1

        # even
        for i in range(len(s)):
            l = i
            r = i + 1

            while l >= 0 and r < len(s) and s[l] == s[r]:
                l -= 1
                r += 1
                ans += 1

        return ans

Complexity

  • Time: $O(n^2)$

  • Space: $O(1)$
    Since we are not using any extra space.

And we are done.