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):
    chars = empty set (or map of char -> index)
    left = 0
    best = 0
    
    for right from 0 to n-1:
        while s[right] in chars:
            remove s[left] from chars
            left++
        // Alternative: if using map, jump left to max(left, map[s[right]] + 1). Without the max, abba gives 3, not 2.
        
        add s[right] to chars (or map)
        best = max(best, right - left + 1)
    
    return best

Hints

  • Use a sliding window. A set answers one yes-or-no question in a single look: is this letter already inside the window?
  • When duplicate found, shrink window from left (set) or jump left past duplicate with max(left, map[c] + 1) (map)
  • Try "abba". When the last 'a' arrives, the first 'a' is already outside the window. If you jump left back to just after it, you count 3, not 2.
  • Track the maximum window size

Complexity questions

Time to check all substrings for uniqueness?

O(n²). There are n starting positions. Each one extends until the first repeat, which can take up to n letters, for example on a string of all different letters. Each Set check is one look, so the total is O(n²) in the worst case.

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 with max(left, index + 1), so left never moves back.

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