003. Longest Substring Without Repeating Characters

Quick Identifier

• Topic: sliding-window
• Pattern: Sliding Window
• Difficulty: Medium
• Companies: Amazon, Google, Meta, Bloomberg, Microsoft
• Frequency: Very High
• LeetCode: 3
• Hint: "Longest substring" with all distinct characters. Expand-contract window where duplicates reset the left edge.

Quick Sights

• Time Complexity: O(n) - Each character is processed once. We use a map to immediately jump the left pointer instead of moving it step-by-step.
• Space Complexity: O(min(n, a)) - Where a is the alphabet size (e.g., 26 for lowercase English letters, 128 for ASCII). Memory is strictly bounded by the character set.
• Core Mechanism: Maintain a "sliding window" [left, right]. Store the last seen index of each character in a Hash Map. If s[right] is already in the map and its index is >= left, jump left to last_seen[s[right]] + 1.

Concept Explanation

As a senior engineer, the way to think about this problem is to visualize a literal physical frame sliding over a sequence of characters. We want to maximize the width of this frame while strictly enforcing a constraint: no two characters inside the frame can be identical.

1. Expansion phase: We smoothly slide the right edge of our frame across the string, adding characters one by one. As long as every character we reveal is new to the current frame, our sequence remains valid and we record its length.
2. Contraction phase: The moment our right edge encounters a character that already exists within our frame, the sequence becomes invalid. We must shrink the frame by pulling the left edge forward to evict the old duplicate.
3. The Optimal Leap: The naive approach moves the left edge step-by-step until the duplicate falls out. But we can be smarter. If we maintain a hash map of the exact index where we last saw every character, we can instantly "teleport" the left edge past the old duplicate's position, skipping unnecessary work.

Important Invariant: At the end of every iteration, the substring bounded by [left, right] is guaranteed to contain only unique characters.

Diagram

This diagram visualizes the flow of the optimal sliding window approach, highlighting exactly when the left pointer is forced to jump forward.

Study Pattern (SDE3+)

• 0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Approaches

• Brute force — check every substring with a set — O(n³) time naive.
• Better — sliding window with a set, step-by-step contraction — O(2n) => O(n) time / O(min(n, alphabet)) space.
• Optimal — sliding window with a last-seen index map to jump left — O(n) time optimal / O(min(n, alphabet)) space. (Always pick this)

Optimal Solution

Go

func lengthOfLongestSubstring(s string) int {
	last := make(map[rune]int)
	best := 0
	left := 0
	
	for right, ch := range s {
		// If we've seen this character recently and its previous 
		// position is inside our current window, jump the left pointer.
		if prior, ok := last[ch]; ok && prior >= left {
			left = prior + 1
		}
		
		// Update the last seen position of the character
		last[ch] = right
		
		width := right - left + 1
		if width > best {
			best = width
		}
	}
	return best
}

JavaScript

function lengthOfLongestSubstring(text) {
	const lastIndex = new Map();
	let best = 0;
	let left = 0;
	
	for (let right = 0; right < text.length; right++) {
		const char = text[right];
		
		// If duplicate found within the current window, leap forward
		if (lastIndex.has(char) && lastIndex.get(char) >= left) {
			left = lastIndex.get(char) + 1;
		}
		
		lastIndex.set(char, right);
		
		const width = right - left + 1;
		if (width > best) {
			best = width;
		}
	}
	return best;
}

Walkthrough

Input: s = "abcabcbb"

Invariant: window [left, right] always has unique characters; left only jumps forward.

Edge Cases

• Empty string: "" (should return 0)
• All distinct characters: "abcdef" (window never shrinks)
• All identical characters: "aaaaaa" (window stays size 1)
• Unicode supplementary pairs if treating UTF-16 (JS) vs runes (Go)

Pitfalls

• Resetting left to 0 on every duplicate instead of moving it forward.
• Off-by-one errors when moving left (it should jump to last_seen + 1, not last_seen).
• Not checking if lastIndex[char] >= left. The duplicate might be outside the current window, in which case we don't care!

Similar Problems

• 567. Permutation in String — fixed window + frequency match.
• 438. Find All Anagrams in a String — sliding frequency signature.
• 209. Minimum Size Subarray Sum — variable window on numeric array.

Mind-Map Tags

#sliding-window #variable-window #unique-chars #last-seen #expand-contract