Expanding and shrinking a window

The standard loop, and why a nested while inside a for is still linear.

Why it works

The standard shape

Nearly every variable window is this loop. Expand unconditionally, then shrink while the window is illegal, then record.

The sentence that makes it work: at the point where you record, the window from left to right is always legal. Everything else is machinery to keep that true.

1def longest_subarray_with_sum_at_most(values, limit):2    """Longest stretch of non-negative values summing to at most limit."""3    left = 04    total = 05    best = 06 7    for right in range(len(values)):8        total += values[right]                 # element enters on the right9 10        while total > limit and left <= right:11            total -= values[left]              # element leaves on the left12            left += 113 14        best = max(best, right - left + 1)     # window is legal here15 16    return best17 18print(longest_subarray_with_sum_at_most([2, 1, 5, 1, 3, 2], 8))

The real question

The mechanics above are fixed. What changes between problems is the state: what the window remembers, and what makes it illegal. For the problem below, decide those two things first, then drop them into this loop.

Trace it· 8 min

Trace the window

Run the loop above on [2, 1, 5, 1, 3, 2] with a limit of 8. After each expansion and any shrinking, give the window total, left, and the window size. The first three steps are done for you to check against; fill in the rest.

right	total	left	size
3
4
5

Code lab· 22 min

Window drills

Three variations on the same loop. max_sum_of_k returns the largest sum of any k consecutive values using a rolling total, not a fresh sum per window. longest_at_most_two_distinct returns the length of the longest stretch containing at most two distinct characters. count_windows_summing_to counts how many stretches of non-negative values sum to exactly the target.

solution.py

Tests

print(max_sum_of_k([2, 1, 5, 1, 3, 2], 3), max_sum_of_k([1, 2], 5))print(longest_at_most_two_distinct("eceba"), longest_at_most_two_distinct("aaaa"))print(count_windows_summing_to([1, 2, 3], 3), count_windows_summing_to([0, 0, 3], 3))

Output

Run tests to see output.

Problem· 22 min

Longest Substring Without Repeating Characters

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1def longest_subarray_with_sum_at_most(values, limit):2 """Longest stretch of non-negative values summing to at most limit."""3 left = 04 total = 05 best = 06 7 for right in range(len(values)):8 total += values[right] # element enters on the right9 10 while total > limit and left <= right:11 total -= values[left] # element leaves on the left12 left += 113 14 best = max(best, right - left + 1) # window is legal here15 16 return best17 18print(longest_subarray_with_sum_at_most([2, 1, 5, 1, 3, 2], 8))

right

total

left

size

print(max_sum_of_k([2, 1, 5, 1, 3, 2], 3), max_sum_of_k([1, 2], 5))print(longest_at_most_two_distinct("eceba"), longest_at_most_two_distinct("aaaa"))print(count_windows_summing_to([1, 2, 3], 3), count_windows_summing_to([0, 0, 3], 3))