Longest Substring Without Repeating Characters

LeetCode's Longest Substring Without Repeating Characters is one of the most popular medium problems on the platform. Given a string s, find the length of the longest substring without repeating characters.

For example, given "abcbad", the answer is 4 (the substring "cbad").

This problem is a textbook application of the sliding window pattern. If you have seen sliding window before, this will click fast. If you have not, this is one of the best problems to learn it on because the window logic is clean and the state tracking is a simple set.

Why brute force is too slow

The obvious approach is to check every possible substring and see if it has all unique characters. For each starting index i, try every ending index j, and check if the substring s[i:j+1] has duplicates.

def length_of_longest_substring_brute(s):
    best = 0
    for i in range(len(s)):
        for j in range(i, len(s)):
            substring = s[i:j + 1]
            if len(substring) == len(set(substring)):
                best = max(best, len(substring))
    return best

This is O(n^3) in the worst case: two nested loops to pick the substring, and building a set to check for duplicates costs up to O(n) per substring. For a string of 50,000 characters, that is way too slow.

Even if you optimize the duplicate check, you are still doing O(n^2) work by checking every pair of start and end positions. The problem is that when you move from one substring to the next, you throw away everything you know and start over.

What if you could reuse the work from the previous window?

The key insight: slide, do not restart

Instead of checking every substring from scratch, keep a window defined by left and right pointers. Expand right to grow the window. When you hit a duplicate character, shrink from the left until the duplicate is gone. Track the characters currently in the window with a set.

Every character enters the set once (when right passes over it) and leaves the set once (when left passes over it). That means the total work across the entire run is O(n), not O(n^2).

This is the "growing window" variant of sliding window. You expand while valid, and you only shrink when the window becomes invalid (when a duplicate is found). The goal is to find the longest valid window, so you want to keep growing as long as possible.

Walking through it step by step

Let's trace through the string "abcbad". We maintain two pointers (left in orange, right in green) and a set of characters currently in the window.

The answer is 4. If we kept going, the window would expand through "cbad" to reach length 4. The key thing to notice: each character was added to the set at most once and removed at most once. Two passes through the data at most, which is O(n).

The code

Here is the complete solution in Python:

def length_of_longest_substring(s):
    seen = set()
    left = 0
    best = 0

    for right in range(len(s)):
        # Shrink: remove characters from the left until no duplicate
        while s[right] in seen:
            seen.remove(s[left])
            left += 1

        # Expand: add the new character
        seen.add(s[right])
        best = max(best, right - left + 1)

    return best

That is the whole thing. Seven lines of real logic. Let's break down what each part does:

1. seen is a set that tracks which characters are currently inside the window.
2. left marks the start of the window. It only moves forward (never backwards).
3. The for loop advances right one position at a time, expanding the window.
4. The while loop fires only when s[right] is already in seen. It removes characters from the left side until the duplicate is cleared.
5. After the duplicate is resolved, we add s[right] to the set and update best.

Complexity analysis

Time: O(n). Each character is added to the set exactly once and removed at most once. The right pointer visits each index once. The left pointer also visits each index at most once. Total operations: at most 2n.

Space: O(min(n, m)) where m is the size of the character set. The set holds at most one of each unique character currently in the window. For ASCII strings, that is at most 128 characters, so effectively O(1). For Unicode, it could be larger, but it is still bounded by the alphabet size.

A common alternative: using a dict for O(n) with fewer operations

Some people use a dict instead of a set, mapping each character to its most recent index. When you hit a duplicate, instead of shrinking one step at a time, you jump left directly past the previous occurrence.

def length_of_longest_substring_dict(s):
    last_seen = {}
    left = 0
    best = 0

    for right in range(len(s)):
        if s[right] in last_seen and last_seen[s[right]] >= left:
            left = last_seen[s[right]] + 1

        last_seen[s[right]] = right
        best = max(best, right - left + 1)

    return best

This avoids the inner while loop entirely. Both are O(n), but the dict version does fewer total operations in practice because it never removes characters one at a time. Either approach is fine in interviews. The set version is easier to understand and follows the standard sliding window template more closely. The dict version is a nice optimization to mention if your interviewer asks about it.

Common mistakes

1. Forgetting to remove characters when shrinking. When you move left forward, the character at the old left position is no longer in the window. If you do not remove it from your set, you will think characters are duplicates when they are not. This is the most common bug.

2. Using if instead of while for shrinking. When you find a duplicate, you might need to shrink multiple positions before the duplicate is cleared. Using if only shrinks once, which can leave the duplicate still in the window.

3. Checking len(set(window)) at each step. This rebuilds the set from scratch on every iteration, turning your O(n) solution back into O(n^2). The whole point of the sliding window is to maintain the set incrementally.

4. Off-by-one on window length. The window from left to right inclusive has right - left + 1 elements. Forgetting the + 1 will make your answer one too small.

The building blocks

This problem decomposes into two reusable pieces that CodeBricks drills independently:

1. Window state tracking

The act of maintaining a data structure (here, a set) that reflects exactly what is inside the current window. Every time the window expands, you add to the state. Every time it shrinks, you remove from the state. The state is always synchronized with the window boundaries.

# When expanding (right moves forward):
seen.add(s[right])

# When shrinking (left moves forward):
seen.remove(s[left])
left += 1

This same pattern appears in Minimum Window Substring (with a frequency dict), Longest Substring with At Most K Distinct Characters (with a dict + size check), and Permutation in String (with a counter). The data structure changes, but the add-on-expand, remove-on-shrink rhythm is always the same.

2. Sliding window mechanics

The two-pointer structure where right always moves forward and left moves forward only when needed. The outer loop drives right. The inner loop (or conditional jump) adjusts left. The key property is that both pointers are monotonically increasing, which guarantees O(n) total work.

left = 0
for right in range(len(s)):
    while window_is_invalid():
        # shrink from left
        left += 1
    # record best

This template is the skeleton of every sliding window problem. What changes between problems is the validity condition and the state tracking. But the expand-and-shrink loop structure stays identical.

These two pieces snap together like Legos here. In harder problems, the same building blocks combine with frequency counting, hash map lookups, or other patterns. Learning them in isolation means you can assemble them on the fly instead of memorizing each problem's solution individually.

Edge cases

Before submitting, verify your solution handles:

• Empty string "": return 0.
• Single character "a": return 1.
• All identical "aaaa": return 1. The window never grows past length 1.
• All unique "abcdef": return 6. The window grows to the full length without ever shrinking.
• Duplicate at the very end "abca": return 3. The window "bca" is the longest.

The sliding window solution handles all of these without special cases.

Related posts

• The Sliding Window Pattern - The general pattern guide covering both shrinking and growing window variants
• Contains Duplicate - The simplest set-based problem, introducing the seen-set building block used here
• Hash Map Patterns - Frequency counting with dicts, which pairs with sliding window in harder substring problems

Reading through this solution is the easy part. Reproducing it from scratch in a week is the hard part. Spaced repetition bridges that gap: you revisit the window-state-tracking and sliding-window-mechanics building blocks at increasing intervals, writing the code each time, until the pattern is automatic.