# 647. Palindromic Substrings

## Description

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.

## Solutions

• class Solution {
public int countSubstrings(String s) {
StringBuilder sb = new StringBuilder("^#");
for (char ch : s.toCharArray()) {
sb.append(ch).append('#');
}
String t = sb.append('$').toString(); int n = t.length(); int[] p = new int[n]; int pos = 0, maxRight = 0; int ans = 0; for (int i = 1; i < n - 1; i++) { p[i] = maxRight > i ? Math.min(maxRight - i, p[2 * pos - i]) : 1; while (t.charAt(i - p[i]) == t.charAt(i + p[i])) { p[i]++; } if (i + p[i] > maxRight) { maxRight = i + p[i]; pos = i; } ans += p[i] / 2; } return ans; } }  • class Solution { public: int countSubstrings(string s) { int ans = 0; int n = s.size(); for (int k = 0; k < n * 2 - 1; ++k) { int i = k / 2, j = (k + 1) / 2; while (~i && j < n && s[i] == s[j]) { ++ans; --i; ++j; } } return ans; } };  • class Solution: def countSubstrings(self, s: str) -> int: t = '^#' + '#'.join(s) + '#$'
n = len(t)
p = [0 for _ in range(n)]
pos, maxRight = 0, 0
ans = 0
for i in range(1, n - 1):
p[i] = min(maxRight - i, p[2 * pos - i]) if maxRight > i else 1
while t[i - p[i]] == t[i + p[i]]:
p[i] += 1
if i + p[i] > maxRight:
maxRight = i + p[i]
pos = i
ans += p[i] // 2
return ans


• func countSubstrings(s string) int {
ans, n := 0, len(s)
for k := 0; k < n*2-1; k++ {
i, j := k/2, (k+1)/2
for i >= 0 && j < n && s[i] == s[j] {
ans++
i, j = i-1, j+1
}
}
return ans
}

• /**
* @param {string} s
* @return {number}
*/
var countSubstrings = function (s) {
let ans = 0;
const n = s.length;
for (let k = 0; k < n * 2 - 1; ++k) {
let i = k >> 1;
let j = (k + 1) >> 1;
while (~i && j < n && s[i] == s[j]) {
++ans;
--i;
++j;
}
}
return ans;
};