# Is Python broken?

• I don't think it can get any faster than this:

``````class Solution:
def lengthOfLongestSubstring(self, S):
for i in xrange(len(S) - 1, 0, -1):
for j in xrange(len(S) - i):
s = S[j : j + i + 1]
if len("".join(set(s))) == len(s):
return len(s)
return 1
``````

However, I am exceeding the time limit. What am I doing wrong?

• maybe the time complexity of you algorithm is O(n^2)?

``````class Solution:
# @return an integer
def lengthOfLongestSubstring(self, s):
if s is None:
return None
if len(s) == 0:
return 0
r_max = 0       # stores the length of the longest substring we currently see
r_temp = ''     # a temporary string stores the current substring without repeating letters
for i in xrange(len(s)):
index = r_temp.find(s[i])
r_temp += s[i]  # so we add s[i] to r_temp
else:               # s[i] is found in r_temp
r_temp = r_temp[index+1:] + s[i]    # starts from found location + 1 with s[i]
# update r_max if r_temp has a larger length
if len(r_temp) > r_max:
r_max = len(r_temp)
return r_max``````

• This post is deleted!

• Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example

• Your solution Complexity is O(N^2) , that's why it times out . You can solve it in O(N) .

``````class Solution:
def lengthOfLongestSubstring(self, s):
hist,mx,cur=dict(),0,0
for i in range(len(s)):
if s[i] not in hist:
hist[s[i]]=-1
if i-hist[s[i]]>cur:
cur+=1
else:
cur=i-hist[s[i]]
mx=max(mx,cur)
hist[s[i]]=i
return mx``````

• Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example

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