Brute force - O(n^3)

```
class Solution(object):
def countSubstrings(self, s):
"""
:type s: str
:rtype: int
"""
res = 0
if s:
n = len(s)
res += n
for l in range(2,n+1): # length ranges from 2 to n including n
for i in range(n-l+1): # start index ranges from 0 to n - l including n - l
if s[i:i+l] == s[i:i+l][::-1]:
res += 1
return res
```

Dynamic Programming O(n^2)

```
class Solution(object):
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
```