647

class Solution {
public:
    int countSubstrings(string s) {
        int n=s.length();
        int dp[n][n];
        memset(dp, 0, sizeof dp);

        int ans=0;
        // Case of 1 character.
        for(int i=0; i<n; i++){
            dp[i][i] = 1;
            ans++;
        }
        // Case of 2 character.
        for(int i=0; i<n-1; i++){
            if(s[i] == s[i+1]){
                dp[i][i+1] = 1;
                ans++;
            }
        }
        // Case of 3+ characters.
        for(int len=3; len<=n; len++){
            for(int start=0; start<n-len+1; start++){
                int end = start+len-1;
                if(s[start] == s[end] && dp[start+1][end-1]){
                    dp[start][end] = 1; ans++;
                }
            }
        }
        return ans;
    }
};