Longest Substring Without Repeating Characters: The Sliding Window Origin Story

⏱ 6 min read

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

This is LeetCode 3, and it is the question that made the sliding window pattern part of the modern interview canon. Before this problem became standard, sliding window was a niche technique mentioned only in competitive programming. After it became a top-asked interview question, the sliding window pattern took its place alongside two pointers, monotonic stack, and binary search as one of the four canonical array techniques every prepared candidate is expected to know.

Examples

Input:  "abcabcbb"
Output: 3  ("abc")

Input:  "bbbbb"
Output: 1  ("b")

Input:  "pwwkew"
Output: 3  ("wke")

Brute force: O(n²) or O(n³)

def length_brute(s):
    best = 0
    for i in range(len(s)):
        seen = set()
        for j in range(i, len(s)):
            if s[j] in seen:
                break
            seen.add(s[j])
            best = max(best, j - i + 1)
    return best

For each starting index, expand rightward while the substring has no duplicates. O(n²) time, O(n) space for the set. Correct, gets partial credit, expected within five minutes.

Sliding window with hash set: O(n)

Maintain a window [left, right) that contains no duplicates. Expand right by including the next character. If the new character is already in the window, advance left past the duplicate before continuing.

def length_sliding(s):
    seen = set()
    left = 0
    best = 0
    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        best = max(best, right - left + 1)
    return best

O(n) time. Each character is added once and removed at most once, so the total work is linear despite the inner while loop. O(min(n, alphabet_size)) space.

Sliding window with last-seen index: O(n) faster constant

Track the most recent index where each character was seen. When a duplicate appears, jump left directly past the previous occurrence — no need to inch forward one character at a time.

def length_optimized(s):
    last_seen = {}
    left = 0
    best = 0
    for right, c in enumerate(s):
        if c in last_seen and last_seen[c] >= left:
            left = last_seen[c] + 1
        last_seen[c] = right
        best = max(best, right - left + 1)
    return best

Same O(n) asymptotically but with better constants (no inner loop, just a constant-time jump). This is the version most polished candidates produce, and the version most interviewers consider “the optimal answer”.

The subtle correctness check: when checking if a character was previously seen, we have to verify that the previous occurrence is still inside the current window (last_seen[c] >= left). If the previous occurrence is to the left of the current window, it does not count as a duplicate within our active substring, so we should not move left.

The sliding window pattern

The sliding window pattern is: maintain a window over an array or string, expanding the right boundary as you iterate, contracting the left boundary when the window violates a constraint. The window’s invariant (no duplicates, at most k distinct characters, sum below threshold) is the problem-specific predicate. The pattern shows up in dozens of problems:

Longest Substring Without Repeating Characters (LC 3) — the prototype
Longest Substring with At Most K Distinct Characters (LC 340)
Longest Repeating Character Replacement (LC 424)
Minimum Window Substring (LC 76)
Permutation in String (LC 567)
Find All Anagrams in a String (LC 438)
Sliding Window Maximum (LC 239) — uses a deque
Subarrays with K Different Integers (LC 992)

The first problem is the cleanest introduction to the pattern, which is why it has earned its place as the canonical example. Once a candidate has internalized the “expand right, contract left, track invariant” structure on this problem, the related problems unlock quickly.

Common mistakes

Forgetting to remove from the set when sliding left. When advancing left, the character at the old left position must be removed from seen. Forgetting this gives wrong answers.
Off-by-one in the window length. The length of [left, right] inclusive is right - left + 1, not right - left. This is a common error in coding under pressure.
The “previous occurrence outside the window” bug. In the optimized version, the check last_seen[c] >= left is essential. Without it, a stale entry from before the current window can incorrectly trigger a window contraction.
Incorrect ASCII/Unicode handling. If the problem says “ASCII printable characters”, a fixed-size array of 128 entries is faster than a hash map. If the problem says “any Unicode”, a hash map is necessary. Knowing when to choose which signals attention to detail.

What interviewers grade

This problem is usually a phone-screen-tier question (medium difficulty, 30-minute slot), and the bar is producing the O(n) solution within the slot with reasonable code quality. The signal layers:

Brute force articulated quickly. Within 3–5 minutes the candidate should describe the O(n²) approach.
Recognize the redundancy. The candidate should articulate that re-checking subsets is wasteful, leading to the sliding window framing.
Clean window code. The sliding window with hash set should come out cleanly. The optimization to last-seen-index is a bonus.
Correctness on edge cases. Empty string, single character, all same characters, all distinct characters. A polished candidate runs through these.
Complexity stated correctly. O(n) time, O(min(n, alphabet_size)) space.

Variations interviewers ask

“At most k distinct characters” instead of “no repeating”. Same window framework with a different invariant. Tests whether the candidate sees the pattern.
“Return the substring, not just the length.” Trivial extension; track the start and end indices.
“What if the string is a stream and you cannot store it all?” Forces the candidate to think about memory and amortized cost.
“What if duplicates are allowed up to count k per character?” Generalizes the predicate. Often combined with longest-repeating-character-replacement.
“Find the K-th longest substring without repeating”. Forces a different algorithmic approach (heap or sorted set), and tests whether the candidate adapts.

Is it asked in 2026?

Yes, ubiquitously. This problem is in the LeetCode top 10 most-asked at FAANG and tier-2 tech firms. It appears in phone screens at virtually every company that does technical interviews, and it is one of the few problems essentially every candidate sees at least once. The optimization journey from brute force to optimal sliding window is the canonical training ground for the pattern.

The problem has not been retired despite being maximally well-known because the bar that was originally medium-hard is now medium, and the question still differentiates candidates who have internalized sliding window from candidates who only know the answer by memorization. The follow-up variations (at most k distinct, minimum window, character replacement) are where the real signal happens in 2026 interviews.

Frequently Asked Questions

What is the time complexity?

O(n) for the sliding window solution. Each character is processed at most twice (once entering the window, once leaving). The amortized cost per character is constant.

What is the space complexity?

O(min(n, alphabet_size)). The hash set stores at most one entry per distinct character in the window, capped by the alphabet size and the input length.

Should I use a set or a hash map?

The set version is simpler. The hash map (last-seen-index) version has slightly better constants because it avoids the inner contraction loop. Either is acceptable; the map version is what most polished candidates produce.

Why is this the prototype for sliding window?

Because the “no duplicates” invariant is the simplest non-trivial predicate that requires the window to contract. Other sliding window problems use more complex predicates, but they all use the same expand-right contract-left structure that this problem introduces.

Is this problem still asked in 2026?

Yes, ubiquitously at phone screens. It remains in the top 10 most-asked across FAANG and tier-2 tech.