~20 minutes · sliding window · Python · Day 9
Tonight's problem is Longest Substring Without Repeating Characters. The ask sounds small: find the longest contiguous piece of a string where no character appears twice. Interviewers like it because the slow solution is easy to describe, but the fast solution depends on one new habit: keep one live window, and repair it only when it breaks.
Grow the window on the right greedily; shrink from the left only until it is valid again. Here valid = no repeated character.
A brute-force version starts a fresh scan at every possible left edge. For each left edge, it grows right until a repeated character appears:
def longest_unique_slow(s):
best = 0
for left in range(len(s)):
seen = set()
for right in range(left, len(s)):
if s[right] in seen: break
seen.add(s[right])
best = max(best, right - left + 1)
return best
That is O(n²): every new left rebuilds work the previous scan mostly knew. Python sets make x in seen average O(1), but restarting the scan still repeats too many checks (Python wiki: time complexity, Python set docs).
Keep one window: s[left:right + 1]. Move right forward one character at a time. If the new character is already inside the window, the window is invalid, so move left forward until that duplicate is gone. Only then update the answer.
The shaded span is the current window: grow right, then keep moving left until the duplicate is gone.
def length_of_longest_substring(s):
left = 0
seen = set() # chars inside the current window
best = 0
for right, ch in enumerate(s):
while ch in seen: # invalid: ch is repeated
seen.remove(s[left]) # shrink from the left
left += 1
seen.add(ch) # valid again
best = max(best, right - left + 1)
return best
The important word is while, not if. In "abba", the second b is fixed by removing a and then the first b. Shrinking once is not enough.
Maximum Erasure Value: find the maximum sum of a contiguous subarray with no repeated values.
Before reading the reveal: what stays the same, and what changes? Say the invariant out loud first.
The shrinking rule is the same. The validity rule is still “no repeated item in the window.” The score changes: instead of tracking window length, carry a running sum. Add the right value when it enters; subtract the left value when it leaves; update best_sum only after the window is valid again.
| Approach | Time | Space |
|---|---|---|
| Brute force (restart a set at each left) | O(n²) | O(n) |
| Sliding window (reuse one live set) | O(n) | O(n) |
Each character enters the set once and leaves the set at most once. That is the whole O(n) argument.
1. What must be true before updating best?
2. Spot the bug in this window update for s = "abba":
if ch in seen:
seen.remove(s[left])
left += 1
seen.add(ch)while ch in seen, because the left edge must move until the duplicate is actually gone.3. Which task asks for this shrinking rule?
4. When do you move left?
Solve Longest Substring Without Repeating Characters in your Notion tracker using the cycle — predict → attempt → compare → encode.
Watch NeetCode — Longest Substring Without Repeating Characters after your attempt, as the compare step. Listen for exactly when he decides to move the left pointer.
Stuck or curious? Ask your teacher (the agent) — that's what it's for.