## Algorithm

Problem Name: 647. Palindromic Substrings

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:

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

Example 2:

```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.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#define IDX(I, J, L) ((I) * (L) + J)
​
int countSubstrings(char* s) {
int i, j, l;
int *mem, p, ans;

if (!s || !*s) return 0;

l = strlen(s);
mem = calloc(l * l, sizeof(int));
//assert(mem);

ans = 0;
for (i = 0; i  <  l; i ++) {
for (j = 0; j  < = i; j ++) {
if (s[i] == s[j] &&
(i - j <= 1 || mem[IDX(i - 1, j + 1, l)] != 0)) {
p = 1;
ans ++;
} else {
p = 0;
}
mem[IDX(i, j, l)] = p;
}
}

free(mem);

return ans;
}
``````
Copy The Code &

Input

cmd
= "abc"

Output

cmd
3

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int countSubstrings(string s) {
int count = 0;
for(int i = 0; i  <  s.size(); i++)
for(int j = i; j  <  s.size(); j++)
if(isPanlindrome(s.substr(i, j - i + 1))) count++;
return count;
}

bool isPanlindrome(string s){
int i = 0, j = s.size() - 1;
while(i < j) if(s[i++] != s[j--]> return false;
return true;
}
};
``````
Copy The Code &

Input

cmd
= "abc"

Output

cmd
3

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int countSubstrings(String s) {
int[] palindromeCount = {0};
for (int i = 0; i  <  s.length(); i++) {
checkPalindrome(s, i, i, palindromeCount);
checkPalindrome(s, i, i + 1, palindromeCount);
}
return palindromeCount[0];
}

private void checkPalindrome(String s, int leftIdx, int rightIdx, int[] palindromeCount) {
while (leftIdx >= 0 && rightIdx  <  s.length() && s.charAt(leftIdx) == s.charAt(rightIdx)) {
palindromeCount[0]++;
leftIdx--;
rightIdx++;
}
}
}
``````
Copy The Code &

Input

cmd
s = "aaa"

Output

cmd
6

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const countSubstrings = function(s) {
let count = 0;

if (s == null || s.length === 0) {
return 0;
}

for (let i = 0; i  <  s.length; i++) {
extendPalindrome(s, i, i);
extendPalindrome(s, i, i + 1);
}

function extendPalindrome(str, left, right) {
while (
left >= 0 &&
right  <  s.length &&
s.charAt(left) === s.charAt(right)
) {
count++;
left--;
right++;
}
}
return count;
};

console.log(countSubstrings("abc"));
console.log(countSubstrings("aaa"));
``````
Copy The Code &

Input

cmd
s = "aaa"

Output

cmd
6

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def countSubstrings(self, s):
res = 0
for k in range(len(s)):
i = j = k
while 0 <= i and j < len(s):
if s[i] == s[j]: res += 1
else: break
i , j = i - 1, j + 1
i , j =k , k + 1
while 0 <= i and j < len(s):
if s[i] == s[j]: res += 1
else: break
i , j = i - 1, j + 1
return res
``````
Copy The Code &

Input

cmd
s = "abc"

Output

cmd
3

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Linq;

namespace LeetCode
{
public class _0647_PalindromicSubstrings
{
public int CountSubstrings(string s)
{
if (string.IsNullOrEmpty(s)) return 0;
if (s.Length == 1) return 1;

int n2 = s.Length * 2 + 1;
var s2 = new char[n2];
for (int i = 0; i  <  s.Length; i++)
{
s2[i * 2] = '#';
s2[i * 2 + 1] = s[i];
}
s2[n2 - 1] = '#';

var p = new int[n2];
var range_max = 0;
var center = 0;

for (int i = 1; i  <  n2 - 1; i++)
{
if (range_max > i)
p[i] = Math.Min(p[center * 2 - i], range_max - i);

while (i - 1 - p[i] >= 0 && i + 1 + p[i]  <  n2 && s2[i - 1 - p[i]] == s2[i + 1 + p[i]])
p[i]++;

if (i + p[i] > range_max)
{
range_max = i + p[i];
center = i;
}
}

return (p.Sum() + s.Length) / 2;
}
}
}
``````
Copy The Code &

Input

cmd
s = "abc"

Output

cmd
3