Python O(n) beats 99.5% with comments


  • 0
    P
    class Solution(object):
        def lengthOfLongestSubstring(self, s):
            """
            :type s: str
            :rtype: int
            """
            char_index = {}
            max_len = 0
            substr_start_index = 0
            for i, char in enumerate(s):
                # retrieves index of dup char, or -1 if it is not a dup
                char_dup_index = char_index.get(char, -1)
                char_index[char] = i
                # if the duplicate is in the current substring...
                if char_dup_index >= substr_start_index:
                    # and current substring > the longest substring so far...
                    if i - substr_start_index > max_len:
                        # we've found a new longest substring!
                        max_len = max(max_len, i - substr_start_index)
                    # the substring now starts at the char after the dup
                    substr_start_index = char_dup_index + 1
            # account for when the longest substring is at the end of "s"
            return max(max_len, len(s) - substr_start_index)
    

Log in to reply
 

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