Two methods:
    expand center and dp

    1. class Solution:
    2.     def countSubstrings(self, s: str) -> int:
    3.         def expandandCount(s, left, right):
    4.             if right >= len(s):
    5.                 return 0
    6.             ans = 0
    7.             while left >= 0 and right < len(s) and s[left] == s[right]:
    8.                 ans += 1
    9.                 left -= 1
    10.                 right += 1
    11.             return ans
    13.         if not s:
    14.             return 0
    15.         n = len(s)
    16.         ans = 0
    17.         for i in range(n):
    18.             ans += expandandCount(s, i, i)
    19.             ans += expandandCount(s, i, i+1)
    20.         return ans
    class Solution:
    def countSubstrings(self, s: str) -> int:
        if not s:
            return 0
        n = len(s)
        dp = [[False] * n for _ in range(n)]

        for i in range(n-1, -1, -1):
            dp[i][i] = True
            for j in range(i+1, n):
                if j == i + 1:
                    dp[i][j] = s[i] == s[j]
                else:
                    dp[i][j] = dp[i+1][j-1] and s[i] == s[j]
        result = sum([sum(dp[i]) for i in range(n)])
        return result