Palindromic Substrings

StringDPManacher

# Solution

Let $n$ be the length of the string s.

# DP

Let dp[i][j] be true if s[i:j+1] is a palindrome.

Complexity

time: $O(n^2)$
space: $O(n^2)$

def countSubstrings(self, s: str) -> int:
n = len(s)
dp = [[False for _ in range(n)] for _ in range(n)]
res = 0

# base case: single letter substrings
for i in range(n):
dp[i][i] = True
res += 1

# base case: double letter substrings
for i in range(n-1):
dp[i][i+1] = (s[i] == s[i+1])
res += dp[i][i+1]

# other cases: substrings of length 3 to n
for length in range(3, n+1):
i, j = 0, length-1
while j < n:
# the state transition
dp[i][j] = (dp[i+1][j-1] and (s[i] == s[j]))
res += dp[i][j]
i += 1
j += 1

return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# Expand around Center

Complexity

time: $O(n^2)$
space: $O(1)$

def countSubstrings(self, s: str) -> int:
n = len(s)
res = 0

def expand_around_center(left, right):
cnt = 0
while left >= 0 and right < n:
if s[left] != s[right]:
break
cnt += 1
# expand around the center
left -= 1
right += 1
return cnt

for i in range(n):
# odd-length palindromes
res += expand_around_center(i, i)
# even-length palindromes
res += expand_around_center(i, i+1)

return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

or simply combine the odd and even lengths into one:

def countSubstrings(self, s: str) -> int:
n = len(s)
res = 0

for i in range(2*n-1):
left = i//2
right = i//2 + i%2
while left >= 0 and right < n and s[left]==s[right]:
left -= 1
right += 1
res += 1

return res

1
2
3
4
5
6
7
8
9
10
11
12
13

# Manacher's Algorithm

Complexity

time: $O(n)$
space: $O(n)$

def countSubstrings(self, s: str) -> int:
res = 0
T = '#'.join('^{}\$'.format(s))
n = len(T)
P = [0 for _ in range(n)]
C = R = 0
max_center = 0
max_len = -1

for i in range(1, n-1):
# w/i right boundary, can save time by copying mirror length
if i < R:
mirror = 2*C - i
P[i] = min(R-i, P[mirror])

# expand around i
while T[i+(1+P[i])] == T[i-(1+P[i])]:
P[i] += 1

# update the center & right
if i + P[i] > R:
C = i
R = i + P[i]

# update the result so far
res += (P[i] + 1)//2

return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28