#动态规划法
class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        #dp[i][j] [i,j]是否为回文串
        dp = [[False]*n for _ in range(n)]

        res = 0
        #dp[i][j]依赖于dp[i+1][j-1]，所以i要从下往上遍历
        for i in range(n-1,-1,-1):
            for j in range(i,n):
                if s[i] == s[j]:
                    if j-i<=1:
                        dp[i][j] = True
                        res += 1
                    else:
                        if dp[i+1][j-1] == True:
                            dp[i][j] = True
                            res += 1
        return res

 

#双指针
class Solution:
    def countSubstrings(self, s: str) -> int:
        res = 0
        n = len(s)
        for i in range(n):
            #以i为中心
            res += self.extend(s,i,i,n)
            #以i,i+1为中心
            res += self.extend(s,i,i+1,n)
        return res
    def extend(self,s,i,j,n):
        res = 0
        while i >= 0 and j < n and s[i] == s[j]:
            i -= 1
            j += 1
            res += 1
        return res