003. Longest Substring Without Repeating Characters

At a Glance

• Topic: sliding-window
• Pattern: Sliding Window
• Difficulty: Medium
• Companies: Amazon, Google, Meta, Bloomberg, Microsoft
• Frequency: Very High
• LeetCode: 3

Problem (one-liner)

Given a string s, return the length of the longest substring that contains no repeated characters.

Recognition Cues

• "Longest substring" with all distinct characters
• Expand–contract window; duplicates reset left edge
• Often asked with ASCII vs Unicode — clarify charset size

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — check every substring with a set — O(n³) time naive.
• Better — sliding window + last-seen index map — O(n) time / O(min(n, alphabet)) space.
• Optimal — same window with right advancing and left = max(left, lastIndex+1) — 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 prior, ok := last[ch]; ok && prior >= left {
			left = prior + 1
		}
		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 (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
• All distinct
• All same character
• Unicode supplementary pairs if treating UTF-16 (JS) vs runes (Go)

Pitfalls

• Resetting left to 0 on every duplicate
• Off-by-one when moving left to last[ch]+1

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.

Variants

• Longest K-distinct substring — window with at most K distinct (hashmap + distinct count).
• With exactly K distinct — AtMost(K) − AtMost(K−1) pattern (often harder problems).

Mind-Map Tags

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