Longest Substring Without Repeating Characters [LC#3]

Given a string s, find the length of the longest substring without repeating characters.

Sliding Window and 2 pointers

• Start with left and right at 0.
• Expand: Move right to add characters and update counts until a repeat is found.
• Shrink: Move left to remove characters until all are unique.
• Track maximum length of the window.
• $T(n) = O(n)$; $S(n) = O(|char set|)$

  def max_substring_without_repetition(s: str) -> int:
      char_count = defaultdict(int)
      left = 0
      ans = 0
      for right in range(len(s)):
          current_char = s[right]
          char_count[current_char] += 1 
          while char_count[current_char]>1:
              char_count[s[left]] -= 1 
              left += 1
          ans = max(ans, right-left+1)
      return ans
  

Optimised Sliding window

• Same as previous approach, but keep track last occurance of all characters seen so far.
• Jump to the next after last occurence whenever a character is encountered again.
• $T(n) = O(n)$; $S(n) = O(|char set|)$

  def max_substring_without_repetition(s: str) -> int:
      last_found_at = {}
      left = 0
      ans = 0
      for right in range(len(s)):
          current_char = s[right]
          if current_char in last_found_at:
              left = max(left, last_found_at[current_char]+1)
          last_found_at[current_char] = right
          ans = max(ans, right - left +1)
      return ans