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?
Here is an accepted python answer, just for your reference.
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]) if index == -1: # s[i] not found in r_temp 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
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
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.