Given a string, your task is to count how many palindromic substrings in this string.
The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.
Example 1:
Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".
Example 2:
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
Note:
- The input string length won’t exceed 1000.
Solution:
Expand from middle
First do it for odd-length.
Then add “ “ inbetween every character and find ones with even length,
class Solution {
public:
int countSubstrings(string s) {
int ans = 0;
for(int i =0; i <s.size();i++){
int cur = 0;
while(i-cur>=0 && i+cur<=s.size()-1 && s[i-cur] == s[i+cur]){
cur++;
}
ans+=cur;
}
string ss = " ";
for(char c: s){
ss+=c;
ss+=' ';
}
s = ss;
for(int i =0; i<s.size();i+=2){
int cur = 0;
while(i-cur>=0 && i+cur<=s.size()-1 && s[i-cur] == s[i+cur]){
cur++;
}
ans += cur/2;
}
return ans;
}
};
Note 1:
No need to add space, just enumerate the 2N-1 possible centers
class Solution(object):
def countSubstrings(self, S):
N = len(S)
ans = 0
for center in xrange(2*N - 1):
left = center / 2
right = left + center % 2
while left >= 0 and right < N and S[left] == S[right]:
ans += 1
left -= 1
right += 1
return ans
Note 2:
Manacher Algorithm:
def countSubstrings(self, S):
def manachers(S):
A = '@#' + '#'.join(S) + '#$'
Z = [0] * len(A)
center = right = 0
for i in xrange(1, len(A) - 1):
if i < right:
Z[i] = min(right - i, Z[2 * center - i])
while A[i + Z[i] + 1] == A[i - Z[i] - 1]:
Z[i] += 1
if i + Z[i] > right:
center, right = i, i + Z[i]
return Z
return sum((v+1)/2 for v in manachers(S))