Sliding window
Grow the right edge, shrink the left edge only when the window breaks its rule, and track the best window seen.
Longest Substring Without Repeating Characters. Return the length of the longest substring of s with no repeated character.
Signals that point here
- "Longest / shortest / count of contiguous subarrays or substrings" with a condition.
- The condition is monotone: if a window is invalid, every larger window containing it is invalid too.
- Fixed-size windows: moving averages, max sum of
kconsecutive elements.
The idea
Each index enters the window once (right edge) and leaves at most once (left edge), so the whole scan is linear even though the window size changes.
Here the window rule is "no repeats". Storing each character's last index lets the left edge jump directly past the repeat instead of stepping one at a time. The last[ch] >= left check matters: a repeat outside the window is not a repeat.
def longest_unique(s: str) -> int:
last: dict[str, int] = {} # char -> last index seen
left = best = 0
for right, ch in enumerate(s):
if ch in last and last[ch] >= left:
left = last[ch] + 1 # jump past the earlier copy
last[ch] = right
best = max(best, right - left + 1)
return bestpublic static class SlidingWindow
{
public static int LongestUnique(string s)
{
var last = new Dictionary<char, int>(); // char -> last index seen
int left = 0, best = 0;
for (int right = 0; right < s.Length; right++)
{
char ch = s[right];
if (last.TryGetValue(ch, out int prev) && prev >= left)
left = prev + 1; // jump past the earlier copy
last[ch] = right;
best = Math.Max(best, right - left + 1);
}
return best;
}
}Complexity
O(n) time; O(min(n, alphabet)) space for the map.
Pitfalls interviewers watch for
- Dropping the
last[ch] >= leftcheck: on"abba"the left edge jumps backwards and the answer comes out 3. - Recomputing the window's validity from scratch each step, which is
O(n²). - Using a window when values can be negative and the condition is a sum: it is no longer monotone. Use prefix sums (next lesson).
Variants worth knowing
- Minimum window substring: count what you still need; shrink while the window stays valid.
- At most
kdistinct characters: shrink while the map has more thankkeys. - Fixed window of size
k: adda[i], subtracta[i - k].
Test it like the interviewer will
longest_unique("abcabcbb")returns3longest_unique("bbbbb")returns1longest_unique("pwwkew")returns3longest_unique("")returns0longest_unique("abba")returns2- Say the cases out loud before you run them. OpenAI's published guide names test coverage as part of the bar; see Sources.
Step through it: longest_unique("abba")
Each step is recorded from an instrumented copy of the Python above, run when the site was built.
Practice
Written for this site to drill the lesson. Not reported interview questions.
- Find the smallest subarray with sum at least
S(all values positive). - Longest substring with at most two distinct characters.
- Return the start index of every anagram of
pinsides.
Check yourself
Why is a variable-size window still O(n)?
Each index is added once and removed at most once; the two edges together move at most 2n times.
When does the window pattern stop working?
When the condition is not monotone, e.g. sums with negative numbers.