# Longest Palindromic Substring

StringDPManacher

Please don't confuse this problem w/ the longest common substring (opens new window) or longest common subsequence.

## # Solution

Let $n$ be the length of string s.

### # Brute Force

Complexity

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

The brute force solution can be further optimized to expand around center by expanding one char at a time in the left and right direction under odd and even cases.

def longestPalindrome(self, s: str) -> str:
if not s: return ""
res = s[0]
for i in range(len(s)):
for j in range(i + 1, len(s)+1):
if self.isPalindrome(s[i:j]) and j - i + 1 > len(res):
res = s[i:j]
return res

def isPalindrome(self, s: str) -> bool:
i = 0
j = len(s) - 1
while i<=j:
if s[i] == s[j]:
i += 1
j -= 1
else:
return False
return True

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

### # DP

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

The state transition is:
dp[i][j] = s[i] == s[j] and dp[i+1][j-1]

The base cases are:
dp[i][i] = True
dp[i][i+1] = s[i] == s[i+1]

Both the state transition and base cases can be combined into dp[i][j] = s[i] == s[j] and (j - i < 3 or dp[i+1][j-1]).

Complexity

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

def longestPalindrome(self, s: str) -> str:
n = len(s)
dp = [[False for _ in range(n)] for _ in range(n)]
res = ""
for i in reversed(range(n)):
for j in range(i, n):
dp[i][j] = s[i] == s[j] and (j - i < 3 or dp[i+1][j-1])
if dp[i][j] and j - i + 1 > len(res):
res = s[i:j+1]
return res

1
2
3
4
5
6
7
8
9
10

### # Expand around Center

A palindrome mirrors around its center. The center for odd-length palindrome is the central character. The center for even-length palindrome is between the central 2 characters. There are $2n - 1$ such centers and expanding around each center takes linear time.

Complexity

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

def longestPalindrome(self, s: str) -> str:
n = len(s)
res = ""
for i in range(n):
# odd-length longest palindrome
odd = self.expandAroundCenter(s, i, i)
if len(odd) > len(res):
res = odd
# even-length longest palindrome
even = self.expandAroundCenter(s, i, i+1)
if len(even) > len(res):
res = even
return res

def expandAroundCenter(self, s: str, l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return s[l+1:r]

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

### # Manacher's Algorithm

This algorithm includes some smart improvements on Expand around Center.

See more at windliang's post (opens new window).

Complexity

time: $O(n)$ (each element is traversed at most twice)
space: $O(n)$

def longestPalindrome(self, s: str) -> str:
# e.g. s = "abba", T = "^#a#b#b#a#$" (odd length) # ^ and$ signs are sentinels appended to each end to avoid bounds checking
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 best result so far
if P[i] > max_len:
max_center = i
max_len = P[i]

start, end = (max_center-max_len)//2, (max_center+max_len)//2
return s[start: end]

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
29
30
31
32