3. Longest Substring Without Repeating Characters

First thought:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        visited_chars = set()
        left = 0
        max_len = 0
        for right, ch in enumerate(s):
            if ch in visited_chars:
                while left < right and ch in visited_chars:
                    visited_chars.remove(s[left])
                    left += 1
            visited_chars.add(ch)
            max_len = max(max_len, right - left + 1)
            
        return max_len

2nd approach: with 2 optimizations

1. use int array to ASCII
1. use dict to imply the next index of left pointer instead of iterating 1-by-1

One bug I made was taking using if chars[idx] instead of if chars[idx] is not None. Note that chars[idx] could be 0

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        chars = [None] * 128
        left, right = 0, 0
        max_len = 0
        while right < len(s):
            idx = ord(s[right])
            if chars[idx] is not None and chars[idx] >= left:
                left = chars[idx] + 1
            max_len = max(max_len, right-left+1)
            chars[idx] = right
            right += 1
            
        return max_len

3. Longest Substring Without Repeating Characters - cocoder39/coco39_LC GitHub Wiki