# Solution by awice

• #### 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 `j-d`-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((j-i)/2 + 1):
if S[i+d] != S[j-d]:
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 whether `S[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 `2N-1` 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 `2N-1` 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 half-length 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 right-most boundary with `center < i`, centered at `center` with right-boundary `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 right-boundary `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 right-boundary 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 when `Z[i] = right - i`. In that case, for each time `Z[i] += 1`, it increments `right`. As right can only be incremented up to `2*N+2` times, in total the algorithm is \$\$O(N)\$\$.

• Space Complexity: We used \$\$O(N)\$\$ additional space to store `A` and `Z`.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.