Skip to content

046 — Longest Substring Without Repeating Characters

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 2 revisions

46 — Longest Substring Without Repeating Characters

LeetCode 3 · Medium. Given a string s, find the length of the longest substring without repeating characters.

🍽️ Intuition

Imagine reading a string left to right while keeping a scoreboard of exactly which letters are currently "in play" in your current clean streak — a run with no repeats. As long as the next letter hasn't shown up yet in that streak, welcome it in and the streak grows. The moment a letter shows up that's already in your current streak, you have a problem: your streak, as it stands, is broken. You don't have to throw the whole streak away, though — you only need to shrink it from the left, kicking people out one at a time, until the earlier copy of that repeated letter is gone. Then the new letter is welcome again.

That's a sliding window whose "state" is simply the set of distinct characters currently between its two edges.

🚩 Pattern-Recognition Cue

"Longest substring" paired with "without repeating characters" is the textbook contiguous + optimize signal from the Sliding Window pattern: a contiguous run (substring), and a superlative (longest) to maximize. The constraint that triggers contraction — "no repeats allowed inside the window" — is checked incrementally as each new character enters, rather than by re-scanning the whole window from scratch.

🐢 Brute Force

For every starting index, grow a substring one character at a time, tracking which characters have been seen, and stop the moment a repeat shows up.

func lengthOfLongestSubstringBruteForce(_ s: String) -> Int {
    let chars = Array(s)
    var best = 0

    for i in 0..<chars.count {
        var seen = Set<Character>()
        for j in i..<chars.count {
            if seen.contains(chars[j]) {
                break
            }
            seen.insert(chars[j])
            best = max(best, j - i + 1)
        }
    }

    return best
}

Big-O: O(n²) time in the worst case — every starting index can scan all the way to the end (e.g. a string with no repeats at all). O(min(n, alphabet size)) extra space for the seen set, rebuilt at every outer step.

🚀 Optimal

Slide a two-pointer window across the string. Keep a set of the characters currently inside the window; when the incoming character is already inside, shrink from the left until it isn't, then let it in.

func lengthOfLongestSubstring(_ s: String) -> Int {
    let chars = Array(s)
    var left = 0
    var window = Set<Character>()
    var best = 0

    for right in 0..<chars.count {
        while window.contains(chars[right]) {
            window.remove(chars[left])
            left += 1
        }
        window.insert(chars[right])
        best = max(best, right - left + 1)
    }

    return best
}

// smoke test
print(lengthOfLongestSubstring("abcabcbb"))   // 3
print(lengthOfLongestSubstring("bbbbb"))      // 1
print(lengthOfLongestSubstring("pwwkew"))     // 3

Big-O: O(n) time — right moves forward n times total, and left also moves forward at most n times total across the whole run, so every character is inserted into and removed from the window at most once. O(min(n, alphabet size)) extra space for the window set.

🔑 The Key Insight

The brute force re-derives, from a blank slate, whether each candidate substring is repeat-free — restarting the seen set fresh at every new starting index, even though the previous starting index already proved most of that same substring was clean. The optimal solution realizes the window never needs to fully reset: when a repeat is found, only the characters between the old left and the earlier occurrence of the repeated character are actually invalid — everything else in the window is still fine. Shrinking one step at a time (instead of restarting from scratch) means each character is only ever added to and removed from the window a single time over the life of the algorithm, which is what turns the repeated O(n) rescans into one O(n) pass.

🔗 Related Chapters

🧸 Memory Sentence

Longest Substring Without Repeating Characters is a clean streak with a bouncer: welcome new letters in from the right, and the moment a repeat shows up, kick people out from the left until the streak is clean again.

✅ Check Your Understanding

The Sliding Window pattern chapter solves this same problem with a [Character: Int] dictionary of last-seen indices, letting left jump directly past the earlier occurrence in one step instead of the while loop above removing characters one at a time from a Set. Both are O(n) overall. Explain why the jump version is still correct even though it can leave "stale" entries in the dictionary for characters that fell out of the window long ago — what guards against left jumping backward on a stale entry?

⬅️ Previous: Best Time to Buy and Sell Stock · Next: Longest Repeating Character Replacement ➡️

Clone this wiki locally