Approach #1: Brute Force [Time Limit Exceeded]
Intuition and Algorithm
For each substring S[i: j+1]
, let's check if it is a palindrome. If it is, we increment 1 to our answer.
To check whether a substring S[i: j+1]
is a palindrome, we check whether every i+d
th character equals the corresponding jd
th character, for d
up to half the length of the substring.
Notably, our brute force method avoids creating new substrings which would use unnecessary space.
Python
class Solution(object):
def countSubstrings(self, S):
def is_palindrome(i, j):
#Is S[i: j+1] a palindrome?
for d in range((ji)/2 + 1):
if S[i+d] != S[jd]:
return False
return True
ans = 0
for i in range(len(S)):
for j in range(i, len(S)):
if is_palindrome(i, j):
ans += 1
return ans
Complexity Analysis

Time Complexity: $$O(N^3)$$, where $$N$$ is the length of the string. After our
for i, j
loops of complexity $$O(N^2)$$, we spend $$O(N)$$ work to check whetherS[i: j+1]
is a palindrome. 
Space Complexity: We need $$O(1)$$ additional space to store the answer.
Approach #2: Center Expansion [Accepted]
Intuition
Every palindrome has a unique center position. For each possible center, we determine all the palindromes that could have that center by scanning from left to right.
Algorithm
Let N = len(S)
. There are 2N1
possible centers for the palindrome: we could have a center at S[0]
, between S[0]
and S[1]
, at S[1]
, between S[1]
and S[2]
, at S[2]
, etc.
To iterate over each of the 2N1
centers, we will move the left pointer every 2 times, and the right pointer every 2 times starting with the second (index 1). Hence, left = center / 2, right = center / 2 + center % 2
.
From here, finding every palindrome starting with that center is straightforward: while the ends are valid and have equal characters, record the answer and expand.
Python
def countSubstrings(self, S):
ans = 0
for center in range(2 * len(S)  1):
left = center // 2
right = left + center % 2
while left >= 0 and right < len(S) and S[left] == S[right]:
ans += 1
left = 1
right += 1
return ans
Complexity Analysis

Time Complexity: $$O(N^2)$$, where $$N$$ is the length of the string. For each center, we could expand potentially up to the bounds of the string. Thus, both the outer loop and the inner loop have $$O(N)$$ complexity.

Space Complexity: We need $$O(1)$$ additional space to store the answer.
Approach #3: Manacher's Algorithm [Accepted]
Intuition
If we knew Manacher's algorithm, a linear time algorithm for determining Z[i]
, the longest halflength of a palindrome with center i
, then computing the number of palindromes would simply be sum((z + 1) // 2 for z in Z)
.
Algorithm
We focus on an explanation of Manacher's algorithm.
To make our implementation easier, we will add '#'
characters, between each character of S
. We also add a '@'
and '$'
characters to the beginning and end of S, to form a working string A
. We assume these characters do not exist originally in S. The problem of finding the longest palindrome at a given center is the same for string S
as it is for A
, so this transformation is justified.
From here on, our position indices will always be in terms of "half indices", represented as full indices in A
. Our loop invariants will be that center, right
is our knowledge of the palindrome with the largest rightmost boundary with center < i
, centered at center
with rightboundary right
. Also, i > center
, and we've already computed all Z[j]
's for j < i
.
When i < right
, we reflect i
about center
to be at some coordinate j = 2 * center  i
. Then, limited to the interval with radius right  i
and center i
, the situation for Z[i]
is the same as for Z[j]
.
For example, if at some time center = 7, right = 13, i = 10
, then for a string like A = '@#A#B#A#A#B#A#$'
, the center
is at the '#'
between the two middle 'A'
's, the right boundary is at the last '#'
, i
is at the last 'B'
, and j
is at the first 'B'
.
Notice that limited to the interval [center  (right  center), right]
(the interval with center center
and rightboundary right
), the situation for i
and j
is a reflection of something we have already computed. Since we already know Z[j] = 3
, we can quickly find Z[i] = min(right  i, Z[j]) = 3
.
Beyond that interval, we can manually expand the palindrome at interval [i  Z[i], i + Z[i]]
(centered at i
with radius Z[i]
) while appropriate. After, we update our knowledge of the palindrome with the largest rightboundary if appropriate.
Python
def countSubstrings(self, S):
def manachers(S):
A = '@#' + '#'.join(S) + '#$'
Z = [0] * len(A)
center = right = 0
for i in range(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))
Complexity Analysis

Time Complexity: $$O(N)$$, where $$N$$ is the length of the string. The outer loop
for i in range(...)
is $$O(N)$$. The while loop only checks the condition more than once whenZ[i] = right  i
. In that case, for each timeZ[i] += 1
, it incrementsright
. As right can only be incremented up to2*N+2
times, in total the algorithm is $$O(N)$$. 
Space Complexity: We used $$O(N)$$ additional space to store
A
andZ
.