# 175 ms Python solution Does any know the time complexity

• 175 ms Python solution Does any know the time complexity

``````def longestPalindrome(self, s):
n=len(s)
if n <2:
return s
Q2 = set()
Q3 = set()
Length = 1
longestP = s[0]
for i in xrange(n-2):
if s[i] == s[i+1]:
if s[i] == s[i+2]:
if s[n-2] == s[n-1]:
if Q3:
Length = 3
longestP = Q3.pop()
if Length<3 and Q2 :
Length = 2
longestP = Q2.pop()
while Q2 or Q3:
if len(Q3)>=len(Q2):
curr = Q3
offset = 1
else:
curr = Q2
offset = 0
start, end = curr.pop()
middle = (start+end)/2

if (middle-(Length+offset)/2<0) or (middle+(Length+offset)/2+1-offset >n-1):
#print "break"
continue

longer = True
for i in reversed(range((end-start-offset+1)/2+offset,(Length+offset)/2+1)):

if s[middle-i] != s[middle+i+1-offset]:
longer = False
break
if not longer:
continue

while True:
i+=1

if middle-i<0 or middle+i+1-offset>=n-1:
break
if s[middle-i] != s[middle+i+1-offset]:
break

i-=1
Length = 2*(i+1)-offset
longestP = (middle-i, middle+i+1-offset)
3. In the best cases the longest candidate is examined firstly. Finding `longestP` cost O(n/2). Then use O(n) time to exclude other sub-strings. So the examine process cost O(1.5*n)
4. In the worst cases, `Length` grows steadily. There will be O(sqrt(2n)) new sub-strings to be added to the sets. So the examine process cost O(2 * sqrt(2n) + n)