3_longest_substring_without_dups.py

"""
Topics:
- sliding window
"""

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        """
        - Sliding window, navigate through the string maybe adding to 
        hash map. 
        - Add chars to set? constant lookup time. remove when left passes
        them. Doesn't matter about handling dups because if there is a dup
        you need to move on until there isn't anyway
        - Count max seq length
        - When you see repeated letter move left pointer until they 
        are all different again

        zxyzxyz seen=z,x max=2
        ^^
        zxyzxyz seen=z,x,y max=3
        ^ ^
        zxyzxyz seen=z,x,y z max=3 Trigger left move until match R then +1
        ^  ^
        zxyzxyz seen=z,x,y x max=3
         ^ ^
        zxyzxyz seen=z,x,y x max=3
         ^  ^
        zxyzxyz seen=z,x,y x max=3
          ^ ^
        zxyzxyz seen=z,x,y x max=3
          ^  ^
        zxyzxyz seen=z,x,y x max=3
           ^ ^
        zxyzxyz seen=z,x,y x max=3
           ^  ^
        zxyzxyz seen=z,x,y x max=3
            ^ ^
        zxyzxyz seen=z,x,y x max=3
            ^ ^
              ^
        """
        seen = set()
        l, r = 0, 0
        max_substring_len = 0
        current_substring_len = 0
        while r < len(s):
            while s[r] in seen:
                seen.remove(s[l])
                l += 1
            seen.add(s[r])
            current_substring_len = r - l + 1
            max_substring_len = max(max_substring_len, current_substring_len)
            r += 1
        return max_substring_len

solution = Solution()
print(solution.lengthOfLongestSubstring("abcabcbb")) # 3    
solution = Solution()
print(solution.lengthOfLongestSubstring("aaabbbcde")) # 4
solution = Solution()
print(solution.lengthOfLongestSubstring("zxyzxyz")) # 3