LC3. Longest Substring Without Repeating Characters

Approach 1: Sliding Window

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        length = 0
        l, r = 0, 0
        seen = set()
 
        for r in range(len(s)):
            while s[r] in seen:
                seen.remove(s[l])
                l += 1
            
            seen.add(s[r])
            length = max(length, r - l + 1)
        
        return length

Complexity

Time: $O(n)$
Space: $O(1)$

Approach 2: Optimized Sliding Window

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        seen = [-1] * 256
        length = 0
        l = 0
 
        for r in range(len(s)):
            rc_seen_i = seen[ord(s[r])]
 
            # The second condition is needed since we're not resetting indexes of all
            # characters between old `l` and new `l` in previous iterations
            if rc_seen_i != -1 and l <= rc_seen_i < r:
                l = rc_seen_i + 1
            
            length = max(length, r - l + 1)
            seen[ord(s[r])] = r
        
        return length

Complexity

Time: $O(n)$ (But avoiding $2n$)
Space: $O(1)$