Is Python broken?


  • 0
    W

    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?


  • 0
    I

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


  • 1
    I

    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

  • 0
    A
    This post is deleted!

  • 0
    S

    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


  • 1
    A

    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

  • 0
    S

    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


Log in to reply
 

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