Longest Substring Without Repeating Characters — LeetCode #3 (Medium)

The Problem

Given a string s, return the length of the longest substring that contains no duplicate characters.

Example

Input: s = "abcabcbb"

Output: 3

The answer is "abc", with the length of 3. Note that
"bca"
and
"cab"
are also correct answers.

Constraints

• 0 <= s.length <= 5 * 10^4
• s consists of English letters, digits, symbols and spaces

The Key Insight

Here's what we're throwing away. When we hit the duplicate 'a', we already knew the window held 'a', 'b', 'c'. We had that information. What if instead of restarting, we just nudged the left edge forward until the duplicate was gone?

That's the sliding window. A left pointer and a right pointer. Right grows the window, left shrinks it. We need instant answers: is this character already in the window? That's a set. Think of a guest list, names only, no duplicates.

You might think to add the character first, then check. Don't. Check first, then add, or you'd match a character against itself. The rule: while right's character is in the set, remove from the left and slide left forward. Then add right's character.

Why It Works

Notice what happened. Both pointers only ever moved right. Every character entered the set once and left once. No backtracking.

Walking Through It

Left and right both start at zero. 'a' is not in the empty set. We add it. Window is one wide. Max is one. Right moves to one. 'b' is not in the set. Add it. Window spans zero to one. Max is two.

Right to two. 'c' is not in the set. Add it. Window is three wide. Max becomes three. Right to three. That's 'a' again. 'a' is already in the set. Duplicate.

Remove 'a' at index zero, slide left to one. 'a' is out of the set. Add the new 'a'. Window spans one to three. Right to four. 'b' is in the set. Remove 'b' at left, slide to two. Add new 'b'. Window is two to four. Max still three.

Right to five. 'c' repeats. Remove 'c' at left, slide to three. Add 'c'. Window three to five. Max still three. Right to six. 'b' is in the set. Remove 'a' at left, slide. 'b' is still there. Remove 'b' too, slide again.

Now 'b' is clear. Add it. Window is just two wide. Right finishes at seven the same way. Max never exceeded three.

Complexity

Each character enters the window once and leaves once. The set holds only the current window. Time and memory both grow with the string's length.

The Code

OK, same logic in Python. We initialize the set, the left pointer, and the running max. The outer loop walks right one step at a time through every character.

The inner while keeps removing from the left until the repeat is out of the set. Then we add the new character and check if this window beats our best.

Hand back the best length we found.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        seen = set()
        left = 0
        max_len = 0
        for right in range(len(s)):
            while s[right] in seen:
                seen.remove(s[left])
                left += 1
            seen.add(s[right])
            max_len = max(max_len, right - left + 1)
        return max_len

Wrap-up

And that's the pattern. Grow until you can't, shrink until you can. You'll see this shape again.

---

📺 Watch the full walkthrough on YouTube: https://youtu.be/dZ395_AbzcA