# [Algorithm] Longest Palindromic Substring

- LeetCode
- Algorithm
- from Blind Curated 75
- Medium
- Link to Question

```
# naive approach
class Solution:
def check_if_palindrome(self, s):
if s == s[::-1]:
return True
return False
def longestPalindrome(self, s: str) -> str:
l = len(s)
# start from the longest substrings, scan through s
# if we got a palindrome, it must be of longest length
# so return and terminate
for i in range(1, l+1):
for j in range(i):
temp_s = s[j:j+l-i+1]
if self.check_if_palindrome(temp_s):
return temp_s
return ''
# Dynamic Programming
# construct a len(s)*len(s) table
# where table[i][j] holds a boolean indicator, of whether
# s[i:j+1] is a palindrome
# Not terribly different from the naive approach,
# but saves lots of computation in the check_if_palindrome step.
class Solution:
def longestPalindrome(self, s) -> str:
if(len(s) == 0 or len(s) == 1):
return s
table = [[False]*len(s) for j in range(len(s))]
# m stores the starting index of the palindrome
m = None
length = 1
# strings of length 1 are always palindrome
for i in range(len(s)):
table[i][i] = True
m = i
# strings of length 2
for i in range(len(s)-1):
if(s[i] == s[i+1]):
table[i][i+1] = True
m = i
length = 2
# strings of length 3 and greater
for l in range(3, len(s)+1):
for i in range(len(s)-l+1):
j = i+l-1
# current string is palindrome if the starting character = ending character
# and the string in between is a palindrome which we check from the table constructed
if s[i] == s[j] and table[i+1][j-1]:
table[i][j] = True
m = i
length = l
return s[m:m+length]
# linear time, Manacher algorithm
# credit: https://leetcode.com/problems/longest-palindromic-substring/discuss/3337/Manacher-algorithm-in-Python-O(n)
class Solution:
# Manacher algorithm
# http://en.wikipedia.org/wiki/Longest_palindromic_substring
def longestPalindrome(self, s):
# Transform S into T.
# For example, S = "abba", T = "^#a#b#b#a#$".
# ^ and $ signs are sentinels appended to each end to avoid bounds checking
T = '#'.join('^{}$'.format(s))
n = len(T)
P = [0] * n
C = R = 0
for i in range(1, n-1):
P[i] = (R > i) and min(R - i, P[2*C - i]) # equals to i' = C - (i-C)
# Attempt to expand palindrome centered at i
while T[i + 1 + P[i]] == T[i - 1 - P[i]]:
P[i] += 1
# If palindrome centered at i expand past R,
# adjust center based on expanded palindrome.
if i + P[i] > R:
C, R = i, i + P[i]
# Find the maximum element in P.
maxLen, centerIndex = max((n, i) for i, n in enumerate(P))
return s[(centerIndex - maxLen)//2: (centerIndex + maxLen)//2]
```

## Leave a comment