```
int countSubstrings(string s) {
int n = s.size(), ret = n;
if (s.size() <= 1) return ret;
// dp[len][i] indicates when s[i] or s[i],s[i+1] is the center of a palindrome
// since we only need the last and current of odd and even length, mod 4.
vector<vector<bool>> dp(4, vector<bool>(n, 0));
// init all 1 when len == 0 and when len == 1
dp[0].assign(n, 1);
dp[1].assign(n, 1);
for (int len = 2; len <= n; ++len)
{
int off = (len - 1) / 2, even = (len+1)%2;
dp[len%4].assign(n, 0); // clear cur state.
for (int i = off; i < n - off - even; ++i)
{
if (dp[(len-2)%4][i] && s[i-off] == s[i + even + off])
{
dp[len%4][i] = 1;
++ret;
}
}
}
return ret;
}
```