class Solution:
def countSubstrings(self, s: str) -> int:
n = len(s)
dp = [[0]*n for _ in range(n)]
res = 0
for i in range(n-1,-1,-1):
for j in range(i,n):
dp[i][j] = s[i] == s[j] and ((j-i+1)<3 or dp[i+1][j-1])
res += dp[i][j]
return res
# faster than 21.72% less than 34.61%
https://leetcode.com/problems/palindromic-substrings/submissions/
C++
Java
Python
C
C
JavaScript
Ruby
Swift
Go
Scala
Kotlin
Rust
PHP