12312

def countSubstrings(self, s):
    """
    :type s: str
    :rtype: int
    """
    cnt = 0  # count of pallindromes encountered 
    if s:
        n   = len(s) 
        # a dynamic programming table, dp[i][j] = True if s[i:j+1] is pallindrome
        dp = [ [ True for j in range(n) ] for i in range(n) ] 

        # each character is pallindrome, so dp[i][i] = True
        # also counting pallindromes of length 1
        for i in range(n):
            dp[i][i]  = True
            cnt      += 1

        for length in range(2,n+1): # length ranges from 2 to n
            for start in range(n):  # start index ranges from 0 to n-1
                i =  start          
                j  = start + length - 1    # end index for a string of length "length" starting at index start 
                if 0 <= i < j < n:         # if indices are within string under consideration
                    dp[i][j] =  False
                    if s[i] == s[j] and dp[i+1][j-1] == True: # if s[i] == s[j] and s[i+1:j] is pallindrome
                        dp[i][j] = True
                        cnt += 1

    return cnt