Given a string s, return the longest palindromic substring in s.
Example 1:
Input: s = "babad" Output: "bab" Note: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd" Output: "bb"
Example 3:
Input: s = "a" Output: "a"
Example 4:
Input: s = "ac" Output: "a"
Constraints:
1 <= s.length <= 1000s consist of only digits and English letters (lower-case and/or upper-case),Source
def longest_palindrom(s):
"""iterative Dynamic Programming (expansion from center)
Time Complexity: O(n²)
Space Complexity: O(n)
"""
if len(s) == 1:
return s
s = '-'.join(s) # This ensure the string will have an odd length (2n-1)
result = ""
for mid, _ in enumerate(s[1:], 1):
max_len = mid if mid <= len(s)//2 else len(s)-1-mid
if max_len < len(result): # exit if length of potential palindrom
break # is smaller than what we already have
x = 1
while x <= max_len and s[mid-x] == s[mid+x]:
x += 1
candidate = s[mid-x+1:mid+x].replace("-", "") # s[L] != s[R] AND s[L:R] ==> L included : R excluded
if len(result) < len(candidate): # but we don't want L either
result = candidate
return result
def longest_palindrom(s):
"""alternative version of above solution (using a helper function)
Note: this is main to help to transition to the solution below
"""
def expand(s, left, right):
"""helper function"""
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left+1:right] # s[L] != s[R] AND s[L:R] --> L included : R excluded
if len(s) == 1:
return s
s = '-'.join(s)
result = ''
for mid,_ in enumerate(s[1:], 1):
max_len = mid if 2*mid <= len(s) else len(s)-1-mid
if max_len < len(result):
break
candidate = expand(s, mid, mid).replace("-", "")
if len(result) < len(candidate):
result = candidate
return result
def longest_palindrom(s):
"""smarter use of above idea --> avoid adding symbol between characters of s
Time Complexity: O(n²)
Space Complexity: O(1)
"""
def expand(s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left+1:right] # s[L] != s[R] AND s[L:R] --> L included : R excluded
if len(s) == 1:
return s
result = ''
for i, _ in enumerate(s): # here we have to start from 0
if len(s)-i <= len(result)//2: # if length of potential palindrom is
break # smaller than what we already have
odd = expand(s, i, i)
even = expand(s, i, i+1)
result = max(result, odd, even, key=len)
return result
s = "babad"
longest_palindrom(s)
'bab'
s = "cbbd"
longest_palindrom(s)
'bb'
s = "a"
longest_palindrom(s)
'a'
s = "ac"
longest_palindrom(s)
'a'
s = "forgeeksaskeegfor"
longest_palindrom(s)
'geeksaskeeg'
Following are implementations of the Manacher algorithm which solves the problem in O(n) Time.
def longest_palindrom(s):
"""special adaptation of Manacher algorithm"""
s_len = len(s)
if s_len == 1:
return s
start, max_len = 0, 1
for i, _ in enumerate(s[1:], 1):
odd = s[i-max_len-1: i+1]
if i-max_len-1 >= 0 and odd == odd[::-1]:
start = i-max_len-1
max_len += 2
continue
even = s[i-max_len: i+1]
if even == even[::-1]:
start = i-max_len
max_len += 1
return s[start: start+max_len]
def longest_palindrom(s):
"""Manacher algorithm
https://www.wikiwand.com/en/Longest_palindromic_substring
https://hackernoon.com/manachers-algorithm-explained-longest-palindromic-substring-22cb27a5e96fmana
"""
string = '-' + '-'.join(s) + '-'
n = len(string)
LPS = [0] * n
mid = 0 # stores the center of the longest palindromic substring until now
right = 0 # stores the right boundary of the longest palindromic substring until now
for i, _ in enumerate(string[1:-1], 1):
mirror_i = mid - (i - mid) # get mirror index of i
if i < right: # check if mirror expanded beyond the left boundary of current longest
LPS[i] = min(right-i, LPS[mirror_i]) # palindrome at center c, if it did P[i] = r-i
L = i - (LPS[i] + 1) # expand at i
R = i + (LPS[i] + 1)
while R < n and L >= 0 and string[L] == string[R]:
LPS[i] += 1
R += 1
L -= 1
if right < i + LPS[i]: # check if the expanded palindrome at i is expanding beyond the
mid = i # right boundary of current longest palindrome at center c
right = i + LPS[i] # if it did, the new center is i
length = max(LPS)
center = LPS.index(length)
start = (center - length)//2
return s[start: start+length]
def longest_palindrom(s):
"""alternative Manacher algorithm
Compute an array with length of max palindrom for each character of s
Note: len(array) = 2n + 1 because the center of a palindrom could be
- a character if len(palindrom) is odd
- in between 2 characters if len(palindrom) is even
Time complexity: O(n)
Space complexity: O(n)
+ details explanations: https://www.akalin.com/longest-palindrome-linear-time
"""
n = len(s)
LPS = [] # list of the lenght of max palindrom of centered around index
max_len = 0
i = 0
while i < n:
# Loop invariant: s[i-max_len:i] is a palindrome.
# Loop invariant: len(arr_pal_lengths) >= 2*i - max_len.
# The code path that increments max_len skips
# the arr_pal_lengths-filling inner-loop.
# Loop invariant: len(arr_pal_lengths) < 2*i + 1.
# Any code path that increments i past max_len - 1 exits the loop early
# and so skips the l-filling inner loop.
if i > max_len and s[i-max_len-1] == s[i]: # check if we can extend the current palindrome.
max_len += 2 # Note: the center of the palindrome remains fixed.
i += 1
continue
LPS.append(max_len) # The current palindrome is as large as it gets, so we add it
# Now to make further progress, we look for a smaller palindrome
# sharing the right edge with the current palindrome.
# If we find one, we can try to expand it and see where that takes us.
# At the same time, we can fill the values for arr_pal_lengths that
# we neglected during the loop above. We make use of our knowledge of
# the length of the previous palindrome (max_len) and the fact that
# the values of arr_pal_lengths for positions on the right half of
# the palindrome are closely related to the values of the corresponding
# positions on the left half of the palindrome.
# Traverse backwards starting from the second-to-last index up
# to the edge of the last palindrome.
right = len(LPS) - 2
left = right - max_len
for j in range(right, left, -1):
d = j - left - 1 # d is the value arr_pal_lengths[j] must have in order for the
# palindrome centered there to share the left edge with the last palindrome
if LPS[j] == d: # We actually want to go to the beginning of the outer loop,
max_len = d # but Python doesn't have loop labels. Instead, we use an
break # else block corresponding to the inner loop, which gets
# # executed only when the for loop exits normally (i.e. no break)
curr_len = min(d, LPS[j]) # We have to bound l[i] because palindromes on the left side
LPS.append(curr_len) # could extend past the left edge of the last palindrome
# # whereas their counterparts won't extend past the right edge
else:
# This code is executed in two cases:
# when the for loop isn't taken at all (max_len == 0)
# or the inner loop was nable to find a palindrome sharing t
# the left edge with the last palindrome.
# In either case, we're free to consider the palindrome centered at s[i]
max_len = 1
i += 1
# We know from the loop invariant that len(l) < 2 * seqLen + 1, so
# we must fill in the remaining values of l.
LPS.append(max_len) # Obviously, the last palindrome we're looking at can't grow any more
# Traverse backwards starting from the second-to-last index up until
# we get arr_pal_lengths to size 2 * seqLen + 1. We can deduce from the
# loop invariants we have enough elements.
lLen = len(LPS)
right = lLen - 2
left = right - (2*n + 1 - lLen)
for i in range(right, left, -1):
d = i - left - 1 # d = distance to left edge of the last palindrome
curr_len = min(d, LPS[i]) # We bound l[i] with min for the same reason as in the inner
LPS.append(curr_len) # loop above.
length = max(LPS)
center = LPS.index(length)
start = (center - length)//2
return s[start: start+length]