ProblemMediumLeetCode #36 min read

Longest Substring Without Repeating Characters

Sliding window with a 'last seen' index — O(n), single pass.

stringssliding-windowhashmap

Intro

Given a string, find the length of the longest substring without repeating characters. The textbook sliding-window problem.

Key insight

Track the last seen index of each character. When you see a repeat inside the window, jump `left` past it.

Approach

1Maintain a 128- or 256-element 'last index seen' array.
2For each right index, if last[c] >= left, set left = last[c] + 1.
3Update last[c] = right and best = max(best, right - left + 1).

Example

Input

s = "pwwkew"

Output

3 ("wke")

Complexity

Time

O(n)

Space

O(min(n, charset))

Code

Snippetpython

def lengthOfLongestSubstring(s):
    last = {}
    best = left = 0
    for right, c in enumerate(s):
        if c in last and last[c] >= left:
            left = last[c] + 1
        last[c] = right
        best = max(best, right - left + 1)
    return best

Pitfalls

Not gating the index update with `last[c] >= left` — leads to left moving backward.
Using a HashMap when a fixed-size int[] is faster (ASCII inputs).

Variants & follow-ups

Longest Substring with At Most K Distinct Characters
Longest Repeating Character Replacement (LC 424)