# Why also TLE at "aaa……..aaaaa" [Python]

• my solution is a force one,testing the substring by different length for len(s) to 1.BUT always TLE at "aaaa…aaaa", i think for this case my method is O(n) ,and i tried to avoid the "aaaa….aaaa" case:

``````if s.startswith("aaaa") :
return s
``````

And, got the same result . Anyone knows the reason? thx~~

``````class Solution:
# @return a string
def longestPalindrome(self, s):
i = length = len(s)
for i in range(i,1,-1):      # i is the length for the current testing substring
for j in range(0,length-i+1): # j is the start point of the substring
pos_start = start = j
pos_end = end = j + i - 1
while start <= end :
if s[start] == s[end]:
start += 1
end -= 1
else:
break
if start > end :
if i == length:  # just to avoid creating a new substring
return s
else:
new_str = s[pos_start:pos_end+1]
return new_str``````

• I have the same problem. Came up with O(n^2), but got TEL error with the "aaaaaaaaaaaaaa...." string.

• My DP solution with O(n^2) also fail to pass due to TLE in the case of string: "esbtzjaaijqkgmtaajpsdfiqtvxsgfvijpxrvxgfumsuprzlyvhclgkhccmcnquukivlpnjlfteljvykbddtrpmxzcrdqinsnlsteonhcegtkoszzonkwjevlasgjlcquzuhdmmkhfniozhuphcfkeobturbuoefhmtgcvhlsezvkpgfebbdbhiuwdcftenihseorykdguoqotqyscwymtjejpdzqepjkadtftzwebxwyuqwyeegwxhroaaymusddwnjkvsvrwwsmolmidoybsotaqufhepinkkxicvzrgbgsarmizugbvtzfxghkhthzpuetufqvigmyhmlsgfaaqmmlblxbqxpluhaawqkdluwfirfngbhdkjjyfsxglsnakskcbsyafqpwmwmoxjwlhjduayqyzmpkmrjhbqyhongfdxmuwaqgjkcpatgbrqdllbzodnrifvhcfvgbixbwywanivsdjnbrgskyifgvksadvgzzzuogzcukskjxbohofdimkmyqypyuexypwnjlrfpbtkqyngvxjcwvngmilgwbpcsseoywetatfjijsbcekaixvqreelnlmdonknmxerjjhvmqiztsgjkijjtcyetuygqgsikxctvpxrqtuhxreidhwcklkkjayvqdzqqapgdqaapefzjfngdvjsiiivnkfimqkkucltgavwlakcfyhnpgmqxgfyjziliyqhugphhjtlllgtlcsibfdktzhcfuallqlonbsgyyvvyarvaxmchtyrtkgekkmhejwvsuumhcfcyncgeqtltfmhtlsfswaqpmwpjwgvksvazhwyrzwhyjjdbphhjcmurdcgtbvpkhbkpirhysrpcrntetacyfvgjivhaxgpqhbjahruuejdmaghoaquhiafjqaionbrjbjksxaezosxqmncejjptcksnoq"

``````class Solution:
# @return a string
def longestPalindrome(self, s):

size = len(s)

if size==0:
return ""

record = [[False for i in range(size)] for i in range(size)]
max_len = 0
start = -1
end = -1

for i in range(size):
for j in range(0,i):

ok = False
if i==j+2:
if s[i]==s[j]:
ok = True
if i==j+1:
if s[i]==s[j]:
ok = True
else:
if record[j+1][i-1] and s[i]==s[j]:
ok = True

record[j][i] = ok

if ok and i-j+1>max_len:
max_len = i-j+1
start = j
end = i

record[i][i] = True

return s[start:end+1]
``````

I suspect that might due to the natural performance issue of python, I'm trying the same implementation with Java now.... (Otherwise, we might need to use O(n) solution such as http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html for python to pass on leetcode )

• It seems if you got a TLE, it only means the total time exceeds the limit. You code just happens to run to "aaaa" test case.

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