Pattern Problem

Longest Substring Without Repeating Characters

“The Club Bouncer”

Time: O(n)

Space: O(min(n, alphabet))

Difficulty: Medium

Pattern: Sliding Window + Hash Map

History

This problem is a staple because it looks deceptively simple until you try to do it efficiently.

At first glance, it feels like a brute-force substring problem. But interviews use it to test whether you can:

Maintain constraints dynamically
Avoid unnecessary recomputation
Recognize the Sliding Window pattern
Reason about invariants instead of nested loops

It is also one of the cleanest demonstrations of how state + window movement can reduce an O(n²) problem to O(n).

Problem Definition

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

A substring must be contiguous.

Core Idea

We want the largest window where all characters are unique.

Instead of restarting every time we hit a duplicate, we: - Track where each character was last seen - Move the left boundary only when necessary - Never move the window backward

The Rule of the Window

At all times, the window $[left, right]$ must satisfy:

All characters inside the window are unique

This rule is the invariant. Every operation exists to restore this rule when it is violated.

How It Works

We scan the string once using two pointers.

$right$ expands the window
$left$ shrinks the window only when duplicates appear
A hash map stores the most recent index of each character

When a duplicate is found: - We jump $left$ to one position after the last occurrence - We never move left backward

The Algorithm Step-by-Step

Initialize:
- $left = 0$
- $seen = \{\}$
- $maxLength = 0$

2. Expand the window by moving $right$

3. If $s[right]$ was seen inside the current window: - Move $left$ to $max(left, seen[s[right]] + 1)$

4. Update $seen[s[right]] = right$

5. Update the answer: - $maxLength = max(maxLength, right - left + 1)$

6. Repeat until the string ends

Time ComplexityO(n)

Each character is visited at most once by right and once by left. No nested loops. No backtracking.

Space ComplexityO(min(n, alphabet))

At most, we store one entry per unique character.

Why the max() Matters

This line is the heart of the solution:

$left = max(left, seen[char] + 1)$

Without $max$ , you risk moving $left$ backward, which breaks the window invariant.

This ensures: - The window only moves forward - Time complexity stays linear - No character is processed more than twice

Approaches

Brute Force

Time: O(n²)Space: O(1)

Check every possible substring and test for duplicates.

Sliding WindowOptimal

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

Track uniqueness dynamically while expanding and shrinking the window.

Code Walkthrough

Real implementations in multiple programming languages. Select a language to view idiomatic code.

1def length_of_longest_substring(s: str) -> int:
2    """Find length of longest substring without repeating characters."""
3    seen: dict[str, int] = {}
4    left = 0
5    max_length = 0
6
7    for right, char in enumerate(s):
8        # If char was seen inside current window, shrink window
9        if char in seen and seen[char] >= left:
10            left = seen[char] + 1
11
12        # Update last seen position
13        seen[char] = right
14
15        # Update max length
16        max_length = max(max_length, right - left + 1)
17
18    return max_length

Python • .py

Real World Use Cases

1Autocomplete systems — Avoid repeated characters when building suggestions
2Streaming analytics — Track unique sessions or events in rolling windows
3Input validation — Enforcing uniqueness constraints efficiently
4Log processing — Detecting longest unique event streaks
5Gateway problem — Teaches patterns used in Minimum Window Substring, At Most K Distinct Characters, and Longest Repeating Character Replacement

Key Insights

This problem is not about strings. It is about maintaining a valid window and updating boundaries only when constraints break.
Once you master this, most sliding window problems feel familiar.
The $max()$ function prevents left from moving backward — this is the critical detail many miss.
Think of the window as a club with a strict bouncer: every character must be unique, and if someone re-enters, everyone before them is kicked out.
The formula $right - left + 1$ gives window size at any moment.

When to Use

Use Sliding Window when you need the best contiguous range, the constraint can be checked incrementally, and you want linear time.

When NOT to Use

Avoid it when the constraint is non-monotonic or you need to consider skipping elements arbitrarily.

Common Interview Pitfalls

Moving left backward
Resetting the window entirely on duplicates
Using nested loops unnecessarily
Forgetting that substrings must be contiguous
Confusing subsequences with substrings

Interview Questions & Answers

Why is Sliding Window the right pattern here?

Because the constraint (unique characters) behaves monotonically as the window expands.

Why not remove characters one by one?

Jumping left directly avoids redundant work and keeps the solution O(n).

What changes if the alphabet is fixed (ASCII)?

Space becomes O(1). Time stays O(n).

How would you modify this for "at most K distinct characters"?

Replace last-seen indices with frequency counts and track the number of distinct keys.

Related Algorithms

Interview

Trapping Rain Water

uses Two Pointers, a cousin of Sliding Window

O(n)

Pathfinding

Breadth-First Search

both use frontier-based exploration

O(V + E)

Watch Longest Substring Without Repeating Characters in Action