1
class Solution {
2
 public:
3
  int countSubstrings(string s) {
4
    int count = s.size();
5
    for (int i = 0; i < s.size(); i++) {
6
      int len1 = expand(s, i, i + 1);
7
      int len2 = expand(s, i, i);
8

9
      // every palindrome found has len/2 total number of palindromes
10
      count += len1 / 2;
11
      count += len2 / 2;
12
    }
13
    return count;
14
  }
15

16
  int expand(string s, int i, int j) {
17
    while (i >= 0 && j < s.size() && s[i] == s[j]) {
18
      i--;
19
      j++;
20
    }
21
    return j - i - 1;
22
  }
23
};