Longest Substring Without Repeating

Difficulty: Medium

Problem

Given a string s, find the length of the longest substring without repeating characters.

Example

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Brute-force approach

Check every substring to see if it has all unique characters.

Steps

  1. Fix a starting index i
  2. Extend substring character by character
  3. Use a Set to check for duplicates
  4. If duplicate found, stop and try next start

Time complexity: O(n²) · Space complexity: O(n)

Trade-offs

  • Checking every substring is O(n²)
  • We restart from scratch at each position
  • Very slow for large strings

Optimal approach

Key insight: Keep a window of unique characters. When duplicate found, shrink from left until unique again.

Sliding window: expand right, shrink left when duplicate found, track max.

Steps

  1. Expand window by moving right
  2. If char already in Set, shrink from left
  3. Add current char to Set
  4. Track maximum window size

Time complexity: O(n) · Space complexity: O(min(n, m))