# 5. Longest Palindromic Substring

Longest Palindromic Substring - LeetCode

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example 1: Input: “babad” Output: “bab” Note: “aba” is also a valid answer.

• code
``````class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
cur = s
for i in range(n):
# odd
l = r = i
while 0 <= l - 1 and r + 1 < n and s[l-1] == s[r+1]:
l -= 1
r += 1
if r - l + 1 > len(cur):
cur = s[l:r+1]

# even
l = i
r = i + 1
if r < n and s[l] == s[r]:
while 0 <= l - 1 and r + 1 < n and s[l-1] == s[r+1]:
l -= 1
r += 1
if r - l + 1 > len(cur):
cur = s[l:r+1]
return cur
``````
• code
``````class Solution:
def longestPalindrome(self, s):
self.maxlen = 0
self.start = 0

for i in range(len(s)):
self.expandFromCenter(s,i,i)
self.expandFromCenter(s,i,i+1)
return s[self.start:self.start+self.maxlen]

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

if self.maxlen < r-l-1:
self.maxlen = r-l-1
self.start = l + 1
``````
• code #slidingwindow
``````class Solution:
def longestPalindrome(self, s: str) -> str:
if s == s[::-1]: return s

window_len = 1
start = 0
for i in range(1, len(s)):
# aaa, from index 1 to index 2, a -> aa or when aa -> aaa, increase max window by 1
if i - window_len >= 0 and s[i - window_len:i+1] == s[i - window_len:i+1][::-1]:
start = i - window_len
window_len += 1

# aba when coming to index 2, we find bab, from a -> bab, increase max window by 2
elif i - window_len >= 1 and s[i - window_len - 1:i+1] == s[i - window_len - 1:i+1][::-1]:
start = i - window_len - 1
window_len += 2

return s[start: start + window_len]
``````

Maintain a max window length, for each index, we check [index - window, index] (containing index, increase the window length by 1) and [index - window -1, index] (increase window length by 2). Suppose the max window we found so far is m, for each index i, we check the substring that ends with current index, with length m+1 or m + 2, see if they are palindromic string. If so, we update start and max window length.