Longest Substring Without Repeating Characters

Problem

Given a string, return the length of the longest substring that contains no repeated characters.

Approach

Keep a sliding window of characters with no repeats, and remember the last index where each character appeared.

When the next character was already seen inside the current window, move the window's start to just after that earlier occurrence. Otherwise the window simply grows.

Checking that the earlier index is inside the window matters: an old occurrence before the window start must not pull the start backwards.

Solution

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last_seen = {}
        start = 0
        best = 0

        for i, char in enumerate(s):
            if char in last_seen and last_seen[char] >= start:
                start = last_seen[char] + 1
            last_seen[char] = i
            best = max(best, i - start + 1)

        return best

Complexity

• Time: O(n): each character is visited once.
• Space: O(min(n, a)), where a is the size of the character set.

Edge cases

• An empty string returns 0.
• A string of one repeated character returns 1.
• Spaces and symbols count as characters too.