Walk me through how a variable-size sliding window finds the longest substring without repeating characters, and why it runs in linear time.

technical-conceptual · Mid level · software-engineering

What the interviewer is really asking

Tests whether the candidate can drive a concrete variable-window algorithm end to end, justify the O(n) bound by amortized pointer movement, and pick the right auxiliary structure.

What to say

• Keep a window [left, right] and a set or map of the characters currently inside it. Advance right one character at a time; if the new character is already in the window, advance left (removing characters from the set) until the duplicate is gone, then record the window length. Track the maximum length seen.
• It's O(n) because of amortized analysis: right moves forward exactly n times, and left only ever moves forward and never past right, so left also advances at most n times total. Each character is added and removed from the set at most once, so the work is linear even though there's a nested-looking inner loop.
• Optimize the contraction by storing each character's last index in a map: on a repeat, jump left directly to one past that index instead of stepping one at a time. Choose the auxiliary structure to match the alphabet — a boolean array for ASCII, a hash map for Unicode.

What to avoid

• Claim the inner while-loop makes it O(n^2) without recognizing that left advances at most n times in total across the whole run.
• Recompute uniqueness by re-scanning the whole current window on every step instead of maintaining the set incrementally.
• Forget to actually remove characters from the set/map as left advances, so stale entries make the window report false duplicates.

Example answers

Strong: I used this to find the longest run of distinct session events in a stream. I kept a map of character to last-seen index so on a repeat I jumped left straight past the previous occurrence rather than stepping one at a time, and I tracked the best length as I went. One pass, linear, no re-scanning.

Weak: I'd check every substring and test whether it has all unique characters, then take the longest one.