Longest Substring Without Repeating Characters

The problem description can be found in LeetCode.

Approach

This is a classic example of a Sliding Window with a Dynamic Size problem.

In fact, we can think of having an imaginary dynamic window of the string (a sub-string), which cannot contain duplicates. We can use a Set to keep track of such duplicates in constant time and we can shrink our window in case we found one. Then, after removing it, we can keep increasing our window to obtain the result.

Solution

from typing import Set


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        chars: Set[str] = set()
        ans = left = 0

        for right, char in enumerate(s):
            while char in chars:
                chars.remove(s[left])
                left += 1

            chars.add(char)
            win_size = right - left + 1
            ans = max(ans, win_size)

        return ans

Complexity

• Time: $O(n)$
• Space: $O(1)$

Where $n$ is the size of the s string.

Regarding the space, since our alphabet is limited to English letters, digits, symbols and spaces, it can be considered as constant. In fact, the size of the chars set that we use to keep track of the repeated characters in the string does not depend on the size of the input string.