Data Structures19 sections · 729 units
Open in Course

Longest Substring - The Idea

When to shrink

You need to track which characters are in the current window. A hash set works well. When you add a character that's already in the set, the window has a repeat.

Shrink from the left until the repeat is gone. Why does this work? The window always contains a valid substring (no repeats). You're finding the longest such window.