# My thought of solving this problem with O(n * log(n)) complexity, please advise

• This problem can be interpreted as:

1. A reduced problem: given string S and constant length L, return the
palindrome (if exist).
-Now I only get O(n^2) solution for this reduced problem, but I believe that there are O(n) solution to this sub problem, since there is already O(n) solution to the original problem O(n) solution

2. A Bi-Search process to find the longest length for the reduced problem. Note that if there exists a palindrome of length N (N>=2), there must be palindrome of length N-2. This makes me think of
Binary-Search method. For example, Given string S length of 10. Then the possible palindrome length falls in two search zones: odd = [1,3,5,7,9] even = [2,4,6,8,10] Then we perform bi-search in these two zone separately.

Because the complexity of bi-search is O(log(n)), so the overall complexity = O(n*log(n))

• Below is my accepted solution of 888 ms:

``````class Solution(object):
def longestPalindrome(self,s):
"""
:type s: str
:rtype: str
"""
def searchForPal(try_len, s):
"""
Give string s, and a length, determin if s contains a palindromic substring of length try_len
input: string s
output: pal or None
"""
L = len(s)
#Shift window of length = try_len
start = 0
end = start + try_len - 1
while 0 <= start <= end <= L-1:
#print "try_len, start, end ",try_len, start, end
#Test if the substring inside this window satisfy Pal condition
st = start
e = end
while start <= st <= e <= end:
if s[st] != s[e]:
#condition not met, move to next window
start += 1
end += 1
break
else:
st += 1
e -=1
if st >= e: #The Pal check finished with no failure
return s[start: end+1]
return ''

temp, s =s, '#'
for c in temp:
s += c + '#'

seen_pal= {1:s[1]} #Pal length, string
search_zone = range(3,len(s)+1,2)

# Use Bi-search to attack the search zone.
#Initialize the seen_pal dict
low = 0
high = len(search_zone) - 1
pal_1 = searchForPal(search_zone[low], s)
pal_2 = searchForPal(search_zone[high], s)
if pal_1 != '':
seen_pal[search_zone[low]] = pal_1
if pal_2 != '':
seen_pal[search_zone[high]] = pal_2

while low < high:
mid = (low + high)/2
if seen_pal.get(search_zone[mid]) is not None:
break
pal = searchForPal(search_zone[mid], s)
if pal == '':
high = mid
else:
seen_pal[search_zone[mid]] = pal
low = mid
maxT = seen_pal[max(seen_pal.keys())]
result = ''
for c in maxT: # O(n)
if c != '#':
result += c
return result``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.