< Back





3. Longest Substring Without Repeating Characters

Sliding window question using a dictionary to keep the last time we've seen a specific character. We
need to maximize for the longest substring we can find without repeating characters. We can track the
last time we've seen a character by maintaining a dictionary of the characters each time we encounter
them, and record the current pointer (right) of our two pointers, left and right, making sure to add
+1 to the right pointer (because we want to skip past the repeated character).

The left pointer will be the maximum of its current value vs the index of the last time we've seen a
specific character. Why the maximum? Well it's possible we see another character repeated from the
past that has a lower index than the current index of the left pointer. There's no point in going
backwards because in that case we've already found another repeating character later in the list.

The solution is as follows:


  from collections import defaultdict

  class Solution:
      def lengthOfLongestSubstring(self, s: str) -> int:
          seen = defaultdict(int)
          l = ans = 0

          for r, char in enumerate(s):
              if char in seen:
                  l = max(seen[char], l)

              ans = max(ans, r - l + 1)
              seen[char] = r + 1

          return ans


_ Time Complexity:

  O(n) - We iterate through the string once.

_ Space Complexity:

  O(n) - We store the last time we've seen each character in a dictionary.