Problem Statement

https://leetcode.com/problems/longest-substring-without-repeating-characters

Solution

This is classical problem for sliding window. Let us keep window with elements [beg: end), where first element is included and last one is not. For example [0, 0) is empty window, and [2, 4) is window with 2 elements: 2 and 3. Let us discuss our algorithm now:

  1. window is set of symbols in our window, we use set to check in $\mathcal{O}(1)$ if new symbol inside it or not.
  2. beg = end = 0 in the beginning, so we start with empty window, also ans = 0 and n = len(s).
  3. Now, we continue, until one of two of our pointers reaches the end. First, we try to extend our window to the right: check s[end] in window and if we can, add it to set, move end pointer to the right and update ans. If we can not add new symbol to set, it means it is already in window set, and we need to move left pointer and move beg pointer to the right.

Complexity

We move both of our pointers only to the left, so time complexity is $\mathcal{O(n)}$. Space complexity is $\mathcal{O}(1)$.

Code

class Solution:
    def lengthOfLongestSubstring(self, s):
        window = set()
        beg, end, ans, n = 0, 0, 0, len(s)
        
        while beg < n and end < n:
            if s[end] not in window:
                if end + 1 < n: window.add(s[end])
                end += 1
                ans = max(ans, end - beg)
            else:
                window.remove(s[beg])
                beg += 1
                
        return ans

If you like the solution, you can upvote it on leetcode discussion section: Problem 0003