Sliding Window (Growing and Shrinking)

When the size isn't fixed

Sometimes you want the longest or shortest stretch that follows a rule. Then the window grows on the right, and shrinks from the left whenever the rule is broken.

Longest stretch with no repeated letter

def longest_unique(s):
    seen = set()
    left = 0
    best = 0
    for right in range(len(s)):
        while s[right] in seen:      # rule broken: shrink from the left
            seen.remove(s[left])
            left += 1
        seen.add(s[right])           # grow on the right
        best = max(best, right - left + 1)
    return best

print(longest_unique("abcabcbb"))
print(longest_unique("bbbb"))
print(longest_unique("pwwkew"))

Output

3
1
3

Each letter enters the window once and leaves at most once, so it's still O(n), even with the inner while loop.

Shortest stretch with a big enough sum

def shortest_with_sum(nums, target):
    left = 0
    total = 0
    best = None
    for right in range(len(nums)):
        total += nums[right]
        while total >= target:
            length = right - left + 1
            if best is None or length < best:
                best = length
            total -= nums[left]
            left += 1
    return best

print(shortest_with_sum([2, 3, 1, 2, 4, 3], 7))

Output

2

Remember: Sliding window = a stretch of neighbouring items. If the items don't have to be next to each other, it's a different kind of problem.

Common mistake: This shrinking trick needs the numbers to be positive. With negative numbers, adding an item can make the total smaller, and the window logic breaks.