LeetCode 3 · Medium · Sliding Window

Longest Substring Without Repeating Characters

Given a string s, return the length of the longest substring (a contiguous run of characters) in which no character appears twice.

O(n)time
O(k)space · k = charset
≤ 2npointer moves

printable ASCII · 0–24 characters · case-sensitive

window hash set · holds exactly s[l..r] · dashed = best so far

public int lengthOfLongestSubstring(String s) { Set<Character> window = new HashSet<>(); // chars in s[l..r] int l = 0, best = 0; for (int r = 0; r < s.length(); r++) { while (window.contains(s.charAt(r))) { window.remove(s.charAt(l)); // shrink from the left l++; } window.add(s.charAt(r)); best = Math.max(best, r - l + 1); } return best;}
l
—
r
—
s.charAt(r)
—
window
[]
best
0

Why it works

  1. Brute force checks every substring for repeats: O(n³), or O(n²) with a fresh set per start index.
  2. Invariant: the window s[l..r] never holds a repeat, and the set holds exactly its characters. Grow r one step; if s[r] is already inside, shrink from the left until it is gone.
  3. Why O(n): l and r only move right, each at most n times, so the inner while does O(n) work in total. The set holds at most k distinct characters: O(min(n, k)) space.
  4. Pitfall: on a repeat, do not restart the window at r. In "dvdf" that loses "vdf". Drop characters from the left only until the old copy is gone.
  5. Faster jumps: store each character's last index in a map and set l = max(l, last[c] + 1), skipping the one-by-one removals. Still O(n), fewer steps.