Longest Substring Without Repeating Characters

This is probably the most-asked sliding window question of all. It is the textbook "longest" window: grow on the right, and when a repeat appears, shrink from the left until it is gone. There is also a faster-looking version that interviewers like to hear as a follow-up.

The problem

Given a string, return the length of the longest substring in which no character appears twice. A substring is a contiguous piece of the string.

• "abcabcbb" → 3. "abc" has no repeats; every piece of length 4 contains some letter twice.
• "abba" → 2. "ab" and "ba" both work; "abb" and "bba" repeat b.

Constraints: 0 ≤ length ≤ 5 × 10⁴. Letters, digits, symbols and spaces may appear.

Clarifying questions

• Is it case-sensitive? Assume yes: "a" and "A" are different characters.
• Length or the substring itself? The length. Returning the substring means also saving the best start.
• Empty string? Return 0.
• What alphabet? Any characters. That matters for the space bound: at most the number of distinct characters.

Approach 1: check every substring

Try every start and every end, and test whether that piece has repeats.

1def longest_unique_brute(s: str) -> int:2    """Check every substring: O(n^3)."""3    best = 04    for start in range(len(s)):5        for end in range(start, len(s)):6            piece = s[start:end + 1]7            if len(set(piece)) == len(piece):8                best = max(best, len(piece))9    return best

Time: O(n³): O(n²) substrings, each costing O(n) to slice and test. Space: O(n).

At n = 5 × 10⁴ that is around 10¹³ character operations. A better brute force grows each start until it meets a repeat and then stops. That costs O(n · d) for an alphabet of d characters: bearable for 26 letters, but on text with thousands of distinct symbols it approaches O(n²), 2.5 × 10⁹ steps. Neither is the linear answer the interviewer wants.

The key insight

The brute force re-reads the same characters again and again. s[3:10] and s[3:11] differ by one character, but it re-checks all eight.

Two facts let a window do better. First, if a substring has a repeat, every longer substring containing it also has one. So when the window start..end has a repeat, no window starting at start and ending later can be valid, and start can move right for good. Second, you only need a set of the characters currently in the window to know whether the entering character is a repeat. Adding a character and removing one are both O(1).

So: move end right one character at a time. If the entering character is already in the set, remove characters from the left until it is not. Then add it, and the window is valid.

Approach 2: a window with a set

1def longest_unique(s: str) -> int:2    """Set-based window: shrink until the entering char is not inside, then add it."""3    in_window: set[str] = set()4    start = 05    best = 06    for end, char in enumerate(s):7        while char in in_window:            # shrink until the old copy is gone8            in_window.remove(s[start])9            start += 110        in_window.add(char)11        best = max(best, end - start + 1)12    return best

Note the order: shrink before adding the entering character. If you added it first, char in in_window would always be true and the loop would empty the window.

Dry run on "abcabcbb":

The answer is 3. At end = 6 and end = 7 the shrink removed two characters each time.

Time: O(n). end moves n times, and start moves at most n times in total over the whole run, so the set sees at most 2n operations. Space: O(min(n, d)), where d is the alphabet size.

Approach 3: jump with a map of last positions

The set version removes the characters before the repeat one at a time. If you store the last index where each character appeared, you can jump start straight past the old copy.

1def longest_unique_jump(s: str) -> int:2    """Last-seen map: jump start past the previous copy in one move."""3    last_seen: dict[str, int] = {}4    start = 05    best = 06    for end, char in enumerate(s):7        if char in last_seen and last_seen[char] >= start:8            start = last_seen[char] + 1      # jump past the old copy9        last_seen[char] = end10        best = max(best, end - start + 1)11    return best

The check last_seen[char] >= start is essential. The map never forgets, so it can hold a position that is already outside the window. Jumping to it would move start backwards.

Dry run on "abba", where the stale position matters:

The answer is 2. Without the >= start check, step 3 would set start = 1, moving it backwards, and report "bba" as length 3.

Time: O(n), with exactly one step per character. Space: O(min(n, d)). Both approaches are O(n); the jump version does less work per repeat, and the set version is easier to get right under pressure. Either is a strong answer.

Edge cases

• Empty string. The loop never runs; the answer is 0.
• One repeated letter, "bbbbb". Each new b removes the old one; the answer is 1.
• All distinct, "abcdef". Nothing is ever removed; the answer is the full length, 6.
• Spaces and symbols. "a b" has characters a, space, b, so the answer is 3. The code treats every character the same way.

Follow-ups

• "Return the substring, not the length." Keep best_start alongside best, and return s[best_start:best_start + best].
• "At most k distinct characters instead of no repeats." Replace the set with a count map and shrink while len(counts) > k. That is the longest-window template from the core lesson.
• "The input is a stream you can't store." The last-seen map version needs only the map and the current index, so it works on a stream.