DP solution with O(n^2) time and memory

```
public int countSubstrings(String s) {
int n = s.length(), count = 0;
boolean[][] dp = new boolean[n][n];
for (int len = 1; len <= n; len++) {
for (int i = 0; i+len-1 < n; i++) {
int j = i+len-1;
dp[i][j] = s.charAt(i) == s.charAt(j) && (i >= j-1 || dp[i+1][j-1]);
if (dp[i][j]) count++;
}
}
return count;
}
```

Count the number of palindrome using ith element as mid point or ith and i+1th element as mid point

```
private int count(String s, int lo, int hi) {
int sum = 0;
while (lo >= 0 && hi < s.length() && s.charAt(lo--) == s.charAt(hi++)) {
sum++;
}
return sum;
}
public int countSubstrings(String s) {
int ans = 0;
for (int i = 0; i < s.length(); i++) {
ans += count(s, i, i) + count(s, i, i+1);
}
return ans;
}
```