A O(n) python solution with explain


  • 0
    C
    class Solution(object):
        def lengthOfLongestSubstring(self, s):
            """
            :type s: str
            :rtype: int
            """
            index = {}  # cache the position of each char in current sub str
            start = 0   # cache the position of the start char in current sub str
            longest, current = 0, 0 # result, and the length of current sub str
            for i, c in enumerate(s):
                if c in index and index[c] >= start:
                    # current c is in current sub str
                    # we shuink the current str
                    current = current + start - index[c]
                    # then update the start position and the index of c
                    start = index[c]+1
                    index[c] = i
                else:
                    # current c is not in current sub str
                    # we update the current str, and see if it's longer than 
                    # the longest sub str
                    index[c] = i
                    current += 1
                    longest = max(longest, current)
            return longest
    

    I think it should be O(n), it's not so fast as I thought though.
    Pls let me know if anywhere it can be improved, thank you.


  • 0

    great solution and detailed explanation, thank you!


Log in to reply
 

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