ORIGINAL TECHNICAL PRACTICE
Explain when a sliding window is valid
How would you find the longest substring containing no repeated characters, and what invariant makes the linear-time approach work?
Written for independent practice. The model answer presents one approach; clarify constraints and explain alternatives.
A REASONED APPROACH
Model answer.
Maintain a window in which every character appears at most once. A map of each character’s latest position lets the left boundary move past a duplicate without rescanning the whole window.
Work through it
- Choose a character model before coding: UTF-16 code units, Unicode code points or user-perceived grapheme clusters can produce different answers.
- Scan the right boundary once. When a character was last seen inside the current window, move left to one position after that occurrence.
- Update the character’s latest position and compare the current window length with the best length. Explain that left never moves backward, including on inputs such as abba.
Tradeoffs to discuss
- The window uses O(k) storage for the distinct symbols encountered. A set-based version may perform more individual removals but is also linear in total movement.
Common pitfalls
- Moving left backward on an old occurrence breaks the invariant. Applying the same window method to arbitrary negative-sum problems is not justified by this proof.