O(n) Python solution, sliding window, 84ms


  • 0
    K

    Use lastAppear to record the index of one character's last appearance. Sliding window's left border is L (not inclusive) and right border is R (inclusive). Characters within sliding window have no duplicates.

    def lengthOfLongestSubstring(self, s):
        L, res, lastAppear = -1, 0, [-1] * 128
        for R in range(len(s)):
            pos = ord(s[R])
            if lastAppear[pos] > L:
                L = lastAppear[pos]
            else:
                res = max(res, R - L)
            lastAppear[pos] = R
        return res

Log in to reply
 

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