Sliding window: variable size

When the window size is not given

Some questions ask for the LONGEST or SHORTEST run that satisfies a rule: the longest stretch of a string with no repeated character, or the shortest run of positive numbers whose sum reaches a target. The window size is now part of the answer, so the window has to grow and shrink.

The pattern: move the right edge forward one item at a time (grow). While the window breaks the rule, move the left edge forward (shrink). When the loop ends, the window is valid again, so update the answer.

left = 0
for right in range(len(items)):
    add items[right] to the window
    while the window is invalid:
        remove items[left] from the window
        left += 1
    answer = best(answer, right - left + 1)

Why it is O(n), not O(n²)

A while loop inside a for loop looks quadratic. But left only moves forward and never passes right, so across the WHOLE run left moves at most n times. Every item is added once and removed at most once: O(n) in total. Counting total moves instead of moves per loop is amortised analysis, from Module 1.

Longest substring without repeating characters

The rule is "no character appears twice in the window". Keep a set of the characters in the window. When s[right] is already in the set, remove s[left] and move left on until the repeat is gone, then add s[right]. O(n) time; the set holds at most one entry per distinct character.

def longest_unique(s):
    seen = set()
    left = best = 0
    for right, c in enumerate(s):
        while c in seen:
            seen.remove(s[left])
            left += 1
        seen.add(c)
        best = max(best, right - left + 1)
    return best

print(longest_unique("abcabcbb"))   # Output: 3  ("abc")
print(longest_unique("pwwkew"))     # Output: 3  ("wke")

A faster variant remembers the last index of each character and jumps left straight past the earlier copy: left = max(left, last[c] + 1). The max matters. In "abba", when the second "a" arrives, its earlier copy at index 0 is already outside the window (left is 2), and jumping to 0 + 1 would move left backwards and make the window wrong.

Shortest subarray with sum at least target

With positive numbers, adding an item always raises the sum and removing one always lowers it. So grow right until the sum reaches the target; then, while it stays at or above the target, record the length and shrink from the left to look for something shorter. O(n) time, O(1) space.

def min_len(target, nums):
    left = total = 0
    best = None
    for right, x in enumerate(nums):
        total += x
        while total >= target:
            if best is None or right - left + 1 < best:
                best = right - left + 1
            total -= nums[left]
            left += 1
    return best if best is not None else 0

print(min_len(7, [2, 3, 1, 2, 4, 3]))   # Output: 2  ([4, 3])

At most k distinct characters

Keep a dict from character to its count in the window. Add s[right]. While the dict has more than k keys, lower the count of s[left], delete the key when it reaches 0, and move left on. The answer is the largest window seen. O(n) time, and O(k) space for the dict.

Why it fails with negative numbers

The method relies on one promise: shrinking a valid window can only make it "less valid", and growing an invalid one can only make it "more invalid". With negative numbers that promise breaks. Removing a negative item RAISES the sum, so "shrink while the sum is at least the target" can stop too early or never see the answer.

print(min_len(6, [1, -5, 6]))   # Output: 0
# Wrong: [6] alone reaches 6, so the right answer is 1.
# The running total goes 1, -4, 2 and never reaches 6.

For sums with negative numbers use prefix sums instead: a hash map for "sum exactly k" (Topic 2), or a monotonic deque over prefix sums for "shortest with sum at least k" (deques come in Module 4).

Common mistakes

• Shrinking with if instead of while, so the window can stay invalid. Fix: shrink with while until it is valid again.
• Updating the answer at the wrong moment. Fix: for "longest", update after shrinking; for "shortest", update inside the shrinking loop.
• Letting left jump backwards with a last-index map ("abba"). Fix: left = max(left, last[c] + 1).
• Forgetting to delete keys whose count is 0, so len(counts) overcounts the distinct characters. Fix: del counts[c] when it reaches 0.
• Using the variable window on numbers that can be negative. Fix: prefix sums with a map.
• Returning float("inf") or None when no window works. Fix: return what the task asks for, often 0.