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