Sliding window

When to reach for it

• The answer is a contiguous subarray or substring.
• The question says longest, shortest, at most k, at least k, or in the last n items or minutes.
• A running summary (a sum, counts of characters, a maximum) can be updated cheaply when one element enters or leaves.
• With a fixed size k, every window shares all but two elements with the previous one.

The core idea

Keep two indexes, left and right, and a summary of what lies between them. Move right forward to grow the window. When the window breaks its rule (too many distinct characters, a sum that is too large) move left forward until the rule holds again, then record the answer. Each index only ever moves forward, so the total work is linear even though there is a loop inside a loop.

A fixed-size window is simpler: add the element that arrives, subtract the one k places back, read the answer. A time-based window (the last five minutes) works the same way with a queue of timestamps, dropping from the front while the oldest entry is too old.

A Python template

from collections import defaultdict

def longest_with_at_most_k_distinct(s, k):
    counts = defaultdict(int)
    best = left = 0
    for right, ch in enumerate(s):
        counts[ch] += 1                       # grow: let s[right] in
        while len(counts) > k:                # shrink until the rule holds
            counts[s[left]] -= 1
            if counts[s[left]] == 0:
                del counts[s[left]]
            left += 1
        best = max(best, right - left + 1)    # the window is valid here
    return best

def max_sum_of_size_k(nums, k):
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]       # one in, one out
        best = max(best, window)
    return best

Time and space

Each element enters the window once and leaves at most once, so a variable window is O(n) time. Space is whatever the summary needs: O(1) for a sum, O(k) or the alphabet size for counts. A sliding maximum keeps a deque of candidates in decreasing order and is still O(n) overall.

Common mistakes

• Recording the answer before the window is valid again, which reports a window that breaks the rule.
• Leaving zero counts in the map, so its size overstates the number of distinct values.
• Using a window when negative numbers break the assumption that a sum only grows as the window grows; prefix sums handle that case.
• Getting the length wrong: it is right - left + 1.
• Recomputing the summary inside the loop, which quietly brings back O(n · k).

How to explain it out loud

Name the window's rule before writing anything: "The window is valid while it holds at most k distinct characters." Then say the two moves: "I let the next character in, and while the rule is broken I move left forward." The rule and the two moves are the whole algorithm, and stating them first is approach planning in Devana's rubric.

Give the complexity argument in one line ("each index only moves forward, so it's O(n)") because the nested loop invites the question. Then point at the edge cases: an empty string, k of zero, a window that never becomes valid. Mentioning them before you are asked counts toward edge cases on the code side of the score.