Sliding Window · LC #3

Longest Substring Without Repeating Characters

Variable-size sliding window with a last-seen map: expand right freely, shrink left only when a duplicate enters the window. Classic interview problem testing window-management fundamentals.

mediumLC #3AMZ★★★GOO★★META★★MSFT★★★AAPL★★TSLA★NFLX★★

Mark as done

Confidence

Ask GPT Practice on LeetCodePractice

Statement

Problem & Approach

Problem statement, sample I/O, and key reasoning.

Find the length of the longest substring without repeating characters.

Sample I/O

Input:  s = "abcabcbb"
Output: 3   ("abc")

Input:  s = "pwwkew"
Output: 3   ("wke")

Intuition

How to Think About It

Intuition

Maintain a window [l, r] that contains no duplicates. When s[r] was already seen inside the current window, jump l to just after the previous occurrence of s[r] - this is the minimal shrink that removes the duplicate. Record the longest valid window seen.

Core Concept

Use a hash map last_seen[char] = index. Scan r from 0 to n-1. If last_seen[s[r]] >= l (duplicate is inside the current window), set l = last_seen[s[r]] + 1. Update last_seen[s[r]] = r. Window length = r - l + 1; track max. Time O(n), Space O(min(n, charset)).

When to use

Any "find longest/shortest subarray satisfying a uniqueness or frequency constraint" problem. The pattern is: expand right, conditionally shrink left, track optimum.

When NOT to use

When the constraint is not about character uniqueness - use a different window validity condition. For fixed-size windows, the simpler fixed-window template is cleaner.

Key Insights

What to Know Cold

Storing last-seen index (not just membership) lets you jump l in O(1) instead of advancing it one step at a time.
Critical guard: only update l if last_seen[s[r]] >= l - the previous occurrence might be outside the current window (harmless).
The window is never explicitly shrunk character-by-character; l jumps directly, making this O(n) not O(n²).
Works for any character set (Unicode) with a hash map; for ASCII-only use a 128-element array for cache friendliness.
The window always represents the longest valid substring ending at r.

1 example

Worked Examples

Variable sliding window - Python

Find longest substring without repeating chars in "abcabcbb".

last_seen map; jump l to last_seen[c]+1 when duplicate detected inside window.

def lengthOfLongestSubstring(s: str) -> int:
    last_seen = {}
    max_len = l = 0
    for r, c in enumerate(s):
        if c in last_seen and last_seen[c] >= l:
            l = last_seen[c] + 1
        last_seen[c] = r
        max_len = max(max_len, r - l + 1)
    return max_len
# "abcabcbb" → 3

Output: 3

Core variable-window template used in dozens of sliding-window variants; O(n) jump-left technique is non-obvious.