Longest Substring Without Repeating Characters

Q: What is the time and space complexity of Longest Substring Without Repeating Characters?

Time O(n), space O(min(n, alphabet)).

Medium

Sliding Window

Hashing & Frequency Maps

Grow a window; when a repeat appears, shrink from the left past it.

Window Trace

left = 0, best = 0, and last_index is empty.

StopSliding windowExport

CH1 left
CH2 right

Problem

Given a string, find the maximum length of a contiguous substring in which every character appears at most once. Return 0 for an empty string. The substring must preserve the original character order and use consecutive positions.

Examples

Input: s = "abcabcbb"

Output: 3

The longest valid substrings include "abc", "bca", and "cab", each with length 3.

Input: s = "pwwkew"

Output: 3

The substring "wke" has three distinct characters; repeated characters prevent any longer valid window.

The Goal

Find the longest run of consecutive characters in s with no character repeated. Return its length, or 0 for an empty string.

Slide a window along s. Grow it on the right, and when a repeat comes in, move the left edge past the earlier copy.

For abcabcbb, the window grows to abc. The next a is a repeat, so the window moves past the first a.

Window invariant

Whenever you measure it, the window holds no repeated character.

Fix the window first, then measure it.

Key Idea: Jump the Left Edge

Keep lastIndex, the latest position of each character. When s[right] was last seen inside the window, every start up to that spot still holds the repeat. So jump left straight to one past it.

In abca, the earlier a is at index 0, so left jumps to 1 and the window is bca.

On a repeat inside the window, set left to the old position plus one.

Old a at 0 means left = 1.

The Algorithm

right reads each character once and left only moves forward, so one pass is enough.

Code

left = 0
best = 0
lastIndex = empty map
for right from 0 through n - 1:
    c = s[right]
    if c is in lastIndex and lastIndex[c] >= left:
        left = lastIndex[c] + 1
    lastIndex[c] = right
    best = max(best, right - left + 1)
return best

The check lastIndex[c] >= left matters. A position from before the window must not drag left back.

Approach	How it fixes repeats	Time	Space
Last-index window	Jump left past the old copy	O(n)	O(min(n, alphabet))
Set window	Drop from the left one by one	O(n)	O(min(n, alphabet))
Check every substring	Test each one from scratch	O(n^2) or worse	O(min(n, alphabet))

Walkthrough

Run it on abcabcbb.

The window grows to abc, length 3. Every character after that is a repeat, so left jumps each time: the window becomes bca, then cab, then abc again, all length 3. The two bs at the end cut it to cb, then b.

The best stays 3.

Checkpoint · predict the next step

Step 8 of 23 on the stage: Read 'a' at 3. It was last seen at 0, inside the window: a repeat.

window "abc" (left 0, right 2) · length 3 · best 3

What does step 9 show?window "bca" (left 1, right 3) · length 3 · best 3window "bc" (left 1, right 2) · length 2 · best 3window "abc" (left 0, right 2) · length 3 · best 3window "ab" (left 0, right 1) · length 2 · best 2

Step through it on the stage

Pitfalls

Jump to lastIndex[c] + 1, not lastIndex[c], or the repeat stays in the window.
Ignore positions before left. If left = 5 and c was last seen at 2, that copy is already outside the window, and left stays at 5.
Measure after the jump, not before.
Test an empty string, one repeated letter, and no repeats at all.

If left = 5 and lastIndex[c] = 2, what happens when c arrives?

Complexity

right visits each character once and left never moves back, so time is O(n), with map lookups that take constant time on average.

The map keeps one entry per distinct character, so space is O(min(n, alphabet)). Call it O(1) only when the alphabet is fixed.

One forward scan

Time

O(n)

Space

O(min(n, alphabet))

Where the time goes

Advance rightEach character enters once.dominantO(n)
Advance leftIt never moves back.dominantO(n)
Map lookup and updateOn average.O(1)
Last-index mapOne entry per distinct character.O(min(n, alphabet))

How it grows

Roughly what that costs

n	10	100	1,000	10,000
O(n)	10	100	1K	10K

One pass, and the window never holds a repeat when it's measured.

In short

Maintain a window and a map of each character's last index. Expand the right edge; if the incoming character was seen inside the current window, jump the left edge just past its previous position. The longest window width seen is the answer.

TimeO(n)SpaceO(min(n, alphabet))

Common mistake

Moving the left pointer to lastIndex instead of lastIndex + 1, or not ignoring stale indices outside the window.

NextLongest Repeating Character Replacement →A window is valid while (length − count of its most frequent char) ≤ k.

Longest Repeating Character ReplacementMedium Minimum Window SubstringHard