Skip to main content

3 - Longest Substring Without Repeating Characters

Difficulty: Medium | Pattern: Sliding Window | Company tags: Amazon, Google, Facebook, Microsoft

Problem Statement​

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

Example 1:

Input: s = "abcabcbb"
Output: 3  ("abc")

Example 2:

Input: s = "bbbbb"
Output: 1  ("b")

Example 3:

Input: s = "pwwkew"
Output: 3  ("wke")

Algorithm Flow​

Solution: Sliding Window + HashMap — O(n), O(min(m,n))​

Key insight: Use a sliding window [left, right]. Track the last seen index of each character. When a duplicate is found, move left to just past the last occurrence.

def lengthOfLongestSubstring(s: str) -> int:
    last_seen = {}
    left = 0
    max_len = 0
    
    for right, c in enumerate(s):
        if c in last_seen and last_seen[c] >= left:
            left = last_seen[c] + 1
        last_seen[c] = right
        max_len = max(max_len, right - left + 1)
    
    return max_len

Dry Run​

s = "abcabcbb"

rightcleftmax_lenaction
0a01no dup
1b02no dup
2c03no dup
3a13a seen at 0 → left=1
4b23b seen at 1 → left=2
5c33c seen at 2 → left=3
6b53b seen at 4 → left=5
7b73b seen at 6 → left=7

Result: 3 ✓

Edge Cases​

  • Empty string → 0
  • All same characters → 1
  • All distinct → n

Complexity​

  • Time: O(n) — each character processed once
  • Space: O(min(m,n)) where m is charset size (26 or 128)

Key Terms​

TermDefinition
Sliding windowA contiguous range [left, right] over the string that expands and contracts while a validity condition holds.
Window invariantThe condition "no repeated character inside [left, right]" that must always hold true.
Last-seen index mapA hash map from character to its most recent index, used to detect and jump past duplicates in O(1).
Two-pointer techniqueUsing two indices (left, right) that both move forward, giving an amortized O(n) traversal.

FAQ​

Q: Why do we check last_seen[c] >= left instead of just c in last_seen? A: A character may have been seen before but already fall outside the current window (to the left of left). Without the >= left check, left could incorrectly move backward.

Q: Can this be solved without extra space? A: Not in true O(1) space for arbitrary Unicode input, but for a bounded alphabet (e.g. ASCII) an array of fixed size (256) replaces the hash map, which is effectively O(1) auxiliary space.

Q: What if the input string is empty? A: The loop never executes, and max_len remains 0, which is the correct answer.

Q: How would the approach change if we needed the actual substring, not just its length? A: Track the left/right bounds whenever max_len updates, then slice s[left:right+1] at the end.

Q: What if we wanted the longest substring with at most k repeating characters instead of zero? A: Generalize to a frequency-count sliding window (like "longest substring with at most K distinct characters") that shrinks the window only when the constraint is violated.

Quick Revision​

  • Problem: find the length of the longest substring with all unique characters.
  • Use a sliding window [left, right] and a hash map of char -> last index seen.
  • On seeing a repeat within the window, jump left to last_seen[c] + 1.
  • Always update last_seen[c] = right and max_len after processing each character.
  • Runs in O(n) time since left and right each move forward at most n times.
  • Space is O(min(m, n)) — bounded by alphabet size or string length, whichever is smaller.
  • Edge cases: empty string → 0; all same character → 1; all distinct → n.
  • Pattern generalizes to many "longest/shortest window satisfying a condition" problems.