Sliding window

Episode 17 Longest Substring Without Repeating Characters

6 min · LeetCode 3 · Java

Title card of Episode 17: Longest Substring Without Repeating Characters

▶ This video is coming to YouTube soon.

LeetCode 3, Longest Substring Without Repeating Characters, solved on screen. Three examples show what counts: a repeat that cuts a stretch short, a string of one letter, and the trap of skipping a letter (a substring has no gaps). Then we watch the brute force grow a set from every start, read its code line by line, and see why it's O(n²). Finally, a sliding window keeps the letters inside it in a HashSet and shrinks from the left on every repeat, finding the answer in one O(n) pass.

What you'll learn

  • What Longest Substring Without Repeating Characters asks, through three examples
  • The brute force: a fresh set from every start, O(n²) time
  • The key idea: a window with no repeats stays that way when it shrinks
  • The sliding window HashSet: O(n) time, O(k) space
  • Why the left edge can jump several letters at once

Chapters

  1. 0:00The problem
  2. 0:14Examples
  3. 0:52Brute force, visualized
  4. 1:39Brute force: the code
  5. 1:55Brute force, line by line
  6. 2:44Sliding window: the idea
  7. 3:02Sliding window, visualized
  8. 3:53Sliding window: the code
  9. 4:09Sliding window, line by line
  10. 5:05Comparing the approaches