My O(n) Solution

  • 0
    class Solution:
    # @return an integer
    def lengthOfLongestSubstring(self, s): 
        len = 0 
        maxLen = 0 
        arr = list(s)
        for index,i in enumerate(arr):
            if i not in arr[index-len:index]:
              len +=1 
              maxLen = max(maxLen,len)
              len = index - (arr[index-len:index].index(i) + index-len)
        return  max(maxLen,len)

  • 0

    I think the solution is not O(n).

    "i not in arr[index-len:index]" is an O(n) operation. Therefore, for example, in the extreme case of the longest substring is the string itself, the "not in" step takes 1, 2, 3, ..., n in each iteration, so the for loop actually takes O(n^2).

    Correct me if I'm wrong.

  • 0

    Agree with ttttian. There is a inner loop hidden in python nifty expression => i not in arr[index-len:index]

Log in to reply

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