Longest Substring Without Repeating Characters

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

A substring is a contiguous sequence of characters within a string.

The string "xyz" is the longest without duplicate characters.

Approach

Use a sliding window with a map of each character's most recent index. Expand the right pointer; when a duplicate is found inside the current window, move the left pointer to one past the last occurrence. Track the maximum window length seen. This handles empty strings and repeated characters efficiently.

Why It Works

The window [left, right] always contains unique characters. When a duplicate appears, moving left past its last position restores the invariant without discarding potential longer substrings. The maximum length over all valid windows is the answer.

Complexity

• Time: O(n)
• Space: O(min(n, alphabet))

Reference Implementation (Python)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last_index = {}
        left = 0
        best = 0
        for right, ch in enumerate(s):
            if ch in last_index and last_index[ch] >= left:
                left = last_index[ch] + 1
            last_index[ch] = right
            best = max(best, right - left + 1)
        return best