# Palindromic Substrings Problem

## Description

LeetCode Problem 647.

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

Example 1:

``````1
2
3
Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".
``````

Example 2:

``````1
2
3
Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
``````

Constraints:

• 1 <= s.length <= 1000
• s consists of lowercase English letters.

## Sample C++ Code

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
int countSubstrings(string s) {
int n = s.size(), cnt = 0;
vector<vector<int>> dp(n, vector<int>(n, 0));

for (int k = 0; k < n; k ++) {
for (int i = 0; i < n-k; i ++) {
int j = i + k;
if (k == 0) {
dp[i][j] = 1;
}
else if (k == 1) {
dp[i][j] = (s[i] == s[j]);
} else {
if (dp[i+1][j-1] == 1 && s[i] == s[j]) {
dp[i][j] = 1;
} else {
dp[i][j] = 0;
}
}
cnt += dp[i][j];

}
}
return cnt;
}
};
``````