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 <= 1000s consists of lowercase English letters.
Solutions
Solution 1: Expand Around Center
We can enumerate the center position of each palindrome and expand outward to count the number of palindromic substrings. For a string of length n, there are 2n-1 possible center positions (covering both odd-length and even-length palindromes). For each center, we expand outward until the palindrome condition is no longer satisfied, and count the number of palindromic substrings.
The time complexity is O(n^2), where n is the length of string s. The space complexity is O(1).
PythonJavaC++GoJavaScript
class Solution:
def countSubstrings(self, s: str) -> int:
ans, n = 0, len(s)
for k in range(n * 2 - 1):
i, j = k // 2, (k + 1) // 2
while ~i and j < n and s[i] == s[j]:
ans += 1
i, j = i - 1, j + 1
return ans(code-box)
class Solution {
public int countSubstrings(String s) {
int ans = 0;
int n = s.length();
for (int k = 0; k < n * 2 - 1; ++k) {
int i = k / 2, j = (k + 1) / 2;
while (i >= 0 && j < n && s.charAt(i) == s.charAt(j)) {
++ans;
--i;
++j;
}
}
return ans;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
/**
* @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;
};(code-box)
Solution 2: Manacher's Algorithm
In Manacher's algorithm, p[i] - 1 represents the maximum palindrome length centered at position i, and the number of palindromic substrings centered at position i is \left \lceil p[i]-1⁄2 \right \rceil.
The time complexity is O(n) and the space complexity is O(n), where n is the length of string s.
PythonJavaC++GoTypeScript
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(code-box)
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;
}
}(code-box)
class Solution {
public:
int countSubstrings(string s) {
string t = "^#";
for (char c : s) {
t += c;
t += '#';
}
t += "$";
int n = t.size();
vector<int> p(n, 0);
int pos = 0, maxRight = 0;
int ans = 0;
for (int i = 1; i < n - 1; ++i) {
if (maxRight > i) {
p[i] = min(maxRight - i, p[2 * pos - i]);
} else {
p[i] = 1;
}
while (t[i - p[i]] == t[i + p[i]]) {
++p[i];
}
if (i + p[i] > maxRight) {
maxRight = i + p[i];
pos = i;
}
ans += p[i] / 2;
}
return ans;
}
};(code-box)
func countSubstrings(s string) int {
t := "^#"
for _, c := range s {
t += string(c)
t += "#"
}
t += "$"
n := len(t)
p := make([]int, n)
pos, maxRight := 0, 0
ans := 0
for i := 1; i < n-1; i++ {
if maxRight > i {
mirror := 2*pos - i
if p[mirror] < maxRight-i {
p[i] = p[mirror]
} else {
p[i] = maxRight - i
}
} else {
p[i] = 1
}
for t[i-p[i]] == t[i+p[i]] {
p[i]++
}
if i+p[i] > maxRight {
maxRight = i + p[i]
pos = i
}
ans += p[i] / 2
}
return ans
}(code-box)
function countSubstrings(s: string): number {
let t = '^#';
for (const c of s) {
t += c + '#';
}
t += '$';
const n = t.length;
const p: number[] = new Array(n).fill(0);
let pos = 0,
maxRight = 0;
let ans = 0;
for (let i = 1; i < n - 1; i++) {
if (maxRight > i) {
p[i] = Math.min(maxRight - i, p[2 * pos - i]);
} else {
p[i] = 1;
}
while (t[i - p[i]] === t[i + p[i]]) {
p[i]++;
}
if (i + p[i] > maxRight) {
maxRight = i + p[i];
pos = i;
}
ans += Math.floor(p[i] / 2);
}
return ans;
}(code-box)
