Workspace

Problem workspace

3 day streakD

Longest Substring Without Repeats

MediumSliding WindowLongest windows

The challenge

Return the length of the longest contiguous substring in which every character appears at most once.

Strings contain ASCII characters; indices are zero-based. C++17 or later.

Example

abcabcbb → 3, from abc; abba → 2.

Use the walkthrough below to inspect the input and each state change.

See No repeats, step by step

Expand, shrink, and inspect the window state.

8 elements · zero-based indices
Sliding window over 8 elementsThe current window is empty. Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.Empty window · L = 0, R = -1a0b1c2a3b4c5b6b7
Current windowRecorded answerOutside window
Left
0
Right
-1
Length
0
Step 01 / 25

Start with an empty window

Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.

left = 0; right = −1

Answer so far

0
View exact input

Input: ["a","b","c","a","b","c","b","b"]

Current window is empty.

Put it into code

Before adding right, the old window is valid. Only the incoming character can introduce a duplicate, so shrink until its frequency is one.

Indices are zero-based. C++ uses C++17 or later.

def longest_unique(s):
    count = {}
    left = best = 0
    for right, char in enumerate(s):
        count[char] = count.get(char, 0) + 1
        while count[char] > 1:
            old = s[left]
            count[old] -= 1
            if count[old] == 0:
                del count[old]
            left += 1
        best = max(best, right - left + 1)
    return best

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap