1
var countSubstrings = function (s) {
2
  const n = s.length;
3
  const dp = [...Array(n)].map(() => Array(n).fill(false));
4
  let count = 0;
5

6
  // Base case: single letter substrings
7
  for (let i = 0; i < n; i++) {
8
    dp[i][i] = true;
9
    count++;
10
  }
11

12
  // Base case: double letter substrings
13
  for (let i = 0; i < n - 1; i++) {
14
    dp[i][i + 1] = s[i] === s[i + 1];
15
    dp[i][i + 1] && count++;
16
  }
17

18
  // substrings longer than 2 chars
19
  for (let len = 3; len <= n; len++) {
20
    let start = 0,
21
      end = start + len - 1;
22

23
    while (end < n) {
24
      dp[start][end] = dp[start + 1][end - 1] && s[start] === s[end];
25
      dp[start][end] && count++;
26
      start++;
27
      end++;
28
    }
29
  }
30
  return count;
31
};