Question link: - LeetCode
class Solution {
public:
int countSubstrings(string s) {
int N=s.length();
bool dp[N][N];
int count=0;
for(int g=0;g<N;g++)
{
for(int i=0,j=g;j<N;j++,i++)
{
if(g==0)
{
dp[i][j]=true;
}
else if(g==1)
{
if(s[i]==s[j])
{
dp[i][j]=true;
}
}
else
{
if(s[i]==s[j] && dp[i+1][j-1]==true)
{
dp[i][j]=true;
}
else
{
dp[i][j]=false;
}
}
if(dp[i][j])
{
count++;
}
}
}
return count;
}
};