A Python solution - 85ms - O(n)


  • 81
    G
    class Solution:
        # @return an integer
        def lengthOfLongestSubstring(self, s):
            start = maxLength = 0
            usedChar = {}
            
            for i in range(len(s)):
                if s[i] in usedChar and start <= usedChar[s[i]]:
                    start = usedChar[s[i]] + 1
                else:
                    maxLength = max(maxLength, i - start + 1)
    
                usedChar[s[i]] = i
    
            return maxLength

  • 0
    L
    This post is deleted!

  • 2
    L

    Brilliant! Seems theres no way to improve it even a little bit. Thanks for sharing


  • 3
    2

    Graceful indeed,but it stiill can be optimised by check wether the remaining string length [start ~ ] are shorter then current max length. if it's, return.


  • 1
    L

    Thumbs up. Thank you


  • 1
    H

    Similar as what I did. I think it might be more compact to add
    maxLen = max(maxLen, i-start+1)
    outside the for loop. Thanks.


  • 1
    S

    if you use " if s[i] in usedChar ", this algorithm won't be O(n), it will be O(n^2)
    tell me if i'm wrong


  • 2
    G

    usedChar is a hashtable, the lookup time is O(1) :)


  • 1
    S

    thx~. actually, i only know that usedchar[key] is O(1) before your comment.
    now, i think you are right.


  • 2
    L

    "Graceful indeed,but it stiill can be optimised by check wether the remaining string length [start ~ ] are shorter then current max length. if it's, return."

    I thought so too at the beginning. But turns out the maxLength can still grow if the remaining string contains chars that are not in the current maxLength string. So return at this point will result in smaller values than the truth.


  • 0
    D

    This is what I tried to do first. But failed in doing.
    Then I came up with another solution.
    Impressive, Thanks!


  • 0

    but why i submit your code and get 300+ms???


  • 25
    M

    If you use 'enumerate', code will be more readable.

    def lengthOfLongestSubstring(self, s):

        used = {}
        max_length = start = 0
        for i, c in enumerate(s):
            if c in used and start <= used[c]:
                start = used[c] + 1
            else:
                max_length = max(max_length, i - start + 1)
                
            used[c] = i
    
        
        return max_length

  • 0
    C

    @Google
    Clear, smart, great solution!
    Thumbs up!


  • 0
    S

    @Google @motal Thanks a lot!


  • 0

    Great solution, thanks a lot!


  • 0
    A

    This solution gave me goosebumps when I finally understood how it worked. Thanks, Thumbs Up


  • 0
    T
    This post is deleted!

  • 0
    B

    How about accessing the index of duplicate letter when necessary?

        max_length = 0
        longest_substring = ''
        
        for letter in s:
            if letter not in longest_substring:
                longest_substring += letter                
            else:
                longest_substring = longest_substring[longest_substring.index(letter)+1:] + letter
                # access the index of duplicate letter in the substring and leave the right side and plus the new letter
            
            if len(longest_substring) > max_length:
                max_length = len(longest_substring)
        
        return max_length

  • 0
    N
    This post is deleted!

Log in to reply
 

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