← Back to Python Examples

Longest Substring Without Repeating Characters

From O(n²) brute force to O(n) sliding window — a fundamental technique that appears everywhere.

Contents

  1. The Problem
  2. Solution 1 — Brute Force O(n²)
  3. The Sliding Window Insight
  4. Solution 2 — Sliding Window O(n)
  5. Solution 3 — Optimized with Last-Seen Index
  6. Summary

1. The Problem

Given a string, find the length of the longest substring that contains no repeating characters.

# "abcabcbb" → 3  (substring "abc")
# "bbbbb"    → 1  (substring "b")
# "pwwkew"   → 3  (substring "wke")
# ""         → 0
A substring is a contiguous sequence of characters, unlike a subsequence which can skip characters. "abc" is a substring of "abcdef"; "ace" is not.

2. Solution 1 — Brute Force O(n²)

Check every possible substring. For each starting position, extend right until a repeat is found.

def length_of_longest_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

print(length_of_longest_brute("abcabcbb"))  # 3

Works, but for a string of length n there are O(n²) substrings to check. On a 10,000-character string that's 50 million iterations.

3. The Sliding Window Insight

The key observation: if the window s[i..j] has no repeats, then when we find that s[j+1] is a repeat, we don't need to restart from i+1. We can slide the left edge forward past the previous occurrence of s[j+1].

# s = "abcabcbb"
#
#  left                 right
#   ↓                    ↓
#   a  b  c  a  b  c  b  b
#
# Window [a,b,c] is valid. Right moves to 'a' — duplicate!
# Instead of starting over, slide left past the old 'a'.
#   New window: [b,c,a]  — still valid, size 3.
# Keep going...

The window never needs to shrink past where the duplicate was last seen. Both pointers only ever move forward — O(n) total.

4. Solution 2 — Sliding Window with Set O(n)

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

    for right in range(len(s)):
        # Shrink left until the window has no duplicates
        while s[right] in seen:
            seen.discard(s[left])
            left += 1
        seen.add(s[right])
        best = max(best, right - left + 1)

    return best

print(length_of_longest_window("abcabcbb"))  # 3
print(length_of_longest_window("pwwkew"))    # 3

5. Solution 3 — Optimized with Last-Seen Index

Instead of a set, store the last-seen index of each character. When a repeat is found, jump left directly past it — no shrinking one step at a time.

def length_of_longest(s):
    last_seen = {}    # char → last index where it appeared
    left = 0
    best = 0

    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            # Jump left past the previous occurrence
            left = last_seen[ch] + 1
        last_seen[ch] = right
        best = max(best, right - left + 1)

    return best

print(length_of_longest("abcabcbb"))  # 3
print(length_of_longest("bbbbb"))     # 1
The check last_seen[ch] >= left is important — a character may have been seen before the current window started. Without it, you'd incorrectly move left backwards.

6. Summary

SolutionTimeSpace
Brute forceO(n²)O(min(n, alphabet))
Sliding window (set)O(n)O(min(n, alphabet))
Sliding window (map)O(n)O(min(n, alphabet))
The sliding window pattern appears in dozens of interview problems. Once you recognize it here, you'll spot it in: minimum window substring, maximum sum subarray of size k, longest subarray with sum ≤ k, and many more.