Longest Substring Without Repeating

Difficulty: Medium

Problem

Imagine reading a string s one character at a time and wanting the longest stretch of consecutive characters in which no character shows up twice. Return the length of that stretch.

Example

Input: s = "abcabcbb"
Output: 3
Explanation: "abc" is a stretch with all distinct characters, and nothing longer manages it here, so the length is 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))

Pseudocode

function lengthOfLongestSubstring(s):
    charSet = empty set (or map of char -> index)
    left = 0
    maxLength = 0
    
    for right from 0 to n-1:
        while s[right] in charSet:
            remove s[left] from charSet
            left++
        // Alternative: if using map, jump left to map[s[right]] + 1
        
        add s[right] to charSet (or map)
        maxLength = max(maxLength, right - left + 1)
    
    return maxLength

Hints

  • Use a sliding window with a set or map to track characters
  • When duplicate found, shrink window from left (set) or jump left past duplicate (map)
  • Track the maximum window size

Complexity questions

Time to check all substrings for uniqueness?

O(n²). O(n²) substrings to check, each with O(n) uniqueness = O(n³), but optimized to O(n²) with early stopping.

Time for sliding window approach?

O(n). Each character visited at most twice (add and remove) = O(n)

Space for the Set in sliding window?

O(min(n,m)). At most min(n, m) characters where m is alphabet size

How can we optimize further using a map?

Store char -> index to jump directly past duplicates. Store char -> index, jump left directly past the duplicate

Check your understanding of Longest Substring Without Repeating

What makes a substring valid?

No repeating characters. A valid substring has all unique characters - no repeats.

Given 'abcabcbb', what's the longest substring without repeating?

'abc' (length 3). 'abc' has length 3 with no repeating characters.

Related problems

Keep practising