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 <= 1000sconsists 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;
}
Input
Output
#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;
}
};
Input
Output
#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++;
}
}
}
Input
Output
#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"));
Input
Output
#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
Input
Output
#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;
}
}
}
Input
Output