Python solution O(n) time and constant space


  • 1
    A
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        first=0
        MaxL=0
        NewMax=0
        for i in range(len(s)):
            if s[i] not in s[first:i]:
                MaxL+=1
            else:
                newfirst=s[first:i].index(s[i])+1
                first+=newfirst
                MaxL=MaxL-newfirst+1
            NewMax=max(MaxL,NewMax)
        return NewMax

  • 0
    L

    In the worst case, if all characters in s are different, then the line

    if s[i] not in s[first:i]:
    

    is O(n^2). This only works as we are only considering some of ASCII characters. What if s is a list of integers, and we are finding the longest sequence with no repeating numbers? I would use a dictionary instead.


  • 0
    A

    it was just not the o(n) solution for the worst condition


  • 0
    S

    This is not a O(n) solution.


Log in to reply
 

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