Longest Substring Without Repeating Characters

Problem Statement

Given a string s, find the length of the longest substring with no repeated characters.

A substring is contiguous — unlike a subsequence, you cannot skip characters.

Input:  s = "abcabcbb"
Output: 3
Why:    "abc"

Input:  s = "bbbbb"
Output: 1
Why:    "b"

Input:  s = "pwwkew"
Output: 3
Why:    "wke" — note "pwke" is a subsequence, not a substring

Intuition

The brute force is to try every starting position and extend until a repeat appears. That is O(n²) and it does a lot of repeated work.

This is the variable-size sliding window, and it differs from the fixed-size kind in one important way.

Why the left edge can jump

This is the part worth slowing down on.

s = "a b c a b c b b"
     0 1 2 3 4 5 6 7

Window is [0..2] = "abc".  Add s[3] = 'a'.
'a' was last seen at index 0.

Any window still containing index 0 now has two as. So every start from 0 is dead — and the next legal start is index 1.

Crucially, you can jump straight there. Sliding the left edge one step at a time would give the same answer, but the jump is what keeps this to a single pass.

s = "abba"

At index 3 ('a'), the map still says 'a' was last seen at index 0.
Naively: left = 0 + 1 = 1.
But left is already 2 (pushed there by the second 'b').
Moving back to 1 would put 'b' in the window twice.

The real-world version

You are reading a shelf of books left to right, collecting a run with no duplicate titles. When you hit a title already in your run, you do not empty your arms and start again. You drop everything up to and including the earlier copy, and carry on from there.

Approach

Watch it run

Solution

def length_of_longest_substring(s: str) -> int:
    """Longest repeat-free substring, using a variable-size window."""
    last_seen: dict[str, int] = {}  # character -> most recent index
    left = 0
    best = 0

    for right, char in enumerate(s):
        # Only jump if the previous copy is INSIDE the current window.
        # max() stops the left edge ever moving backwards.
        if char in last_seen and last_seen[char] >= left:
            left = last_seen[char] + 1

        last_seen[char] = right

        # Both edges are inclusive, hence the + 1.
        best = max(best, right - left + 1)

    return best


def length_of_longest_substring_set(s: str) -> int:
    """Set version — shrinks one step at a time instead of jumping.
    Same O(n) total, since each character is removed at most once."""
    window: set[str] = set()
    left = 0
    best = 0

    for right, char in enumerate(s):
        while char in window:
            window.remove(s[left])
            left += 1

        window.add(char)
        best = max(best, right - left + 1)

    return best

Complexity Analysis

• Time — the right edge moves n times and the left edge only ever moves forward, so it also moves at most n times in total. Two pointers, each crossing the string once.
• Space — the map holds at most one entry per distinct character. For lowercase English that is 26 regardless of input length; in general it is bounded by both the alphabet size and n.

Edge Cases

Related Problems

• Maximum Average Subarray I — the fixed-size window, where the left edge moves every step
• Is Subsequence — subsequences, where skipping is allowed
• Two Sum — the same falsy-zero trap with a Map
• Valid Palindrome — two pointers converging instead of sliding