Solution to Leetcode 3 Longest Substring Without Repeating Characters

soln_lc3.py

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        charSet = set()
        left = 0 
        maxLen = 0
        for right in range(len(s)):
            while s[right] in charSet:
                charSet.remove(s[left])
                left += 1
            charSet.add(s[right])
            maxLen = max(maxLen, len(charSet))
        return maxLen

This solution has a higher complexity $O(n^2)$ because the in operation in deque takes $O(m)$ where m is the length of the substring.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        import collections
        dq = collections.deque([])
        left = 0
        maxLen = 0
        for right in range(len(s)):
            while s[right] in dq:
                dq.popleft()
            dq.append(s[right])
            maxLen = max(maxLen, len(dq))
        return maxLen