Practice: Longest Substring
No repeated characters.
Find the length of the longest part of a string with no repeated characters. In ABCABCBB, the answer is three, ABC. Pause, and think about a window that grows and shrinks.

- Longest stretch with no repeats
- abcabcbb → 3
- Grow and shrink a window
A growing window
Start marks the left edge of the window. A dictionary remembers where we last saw each character. When we meet a character that's already inside the window, we move start just past its last position. Then we record the new position, and the best length so far. Run it. Three, one, and three.
def longest_unique(s):
last = {}
start = best = 0
for i, ch in enumerate(s):
if ch in last and last[ch] >= start:
start = last[ch] + 1
last[ch] = i
best = max(best, i - start + 1)
return best
for s in ["abcabcbb", "bbbbb", "pwwkew"]:
print(s, "->", longest_unique(s))abcabcbb -> 3 bbbbb -> 1 pwwkew -> 3
How to spot a window problem
Look for words like longest, shortest, or best, together with substring, or subarray, or in a row. Those are strong hints for a sliding window. The data is in one line, and you care about a continuous stretch of it.
| key | value |
|---|---|
| Longest / shortest | a strong hint |
| Substring / subarray | continuous stretch |
| In a row | consecutive items |
| Track the edges | start and end |
Summary
A growing window, plus a dictionary of last positions, finds the longest stretch without repeats in O of N. Next, prefix sums. Precompute once, then answer instantly.
Key takeaways- Move start past the repeat
- Remember last positions
- O(n)