Variable-size sliding window in Python

Why this matters

Many questions ask for a stretch of values whose length is not given. "What is the longest run of days where the total spend stays under a limit?" "What is the shortest run of tasks that adds up to at least a target?" "What is the longest piece of text that uses at most two different letters?" The answer is a window, but nobody says how long it is. The previous lesson covered windows whose length is fixed. This lesson covers windows that stretch and shrink.

The direct method tries every start and every end, then checks each stretch. For a list of 10,000 values, that is about 50 million stretches to check. A variable-size window does one pass. A right edge moves forward and takes in one value at a time. A left edge moves forward only when the window breaks a rule. Each edge moves forward at most once per value, so the total work is O(n), which means it grows in step with the number of values.

Here, the window is always a run of neighbouring values, as in the previous lesson. The new part is that the left edge decides when to move.

The idea

Two edges and a window

Keep two positions, left and right. The window is the values from left to right, with both ends included. Each step does one of two things.

• Grow: move right one step to the right, and add the value it now points to.
• Shrink: move left one step to the right, and remove the value it leaves behind.

The loop moves right once per step. After each growth, it shrinks the window while the rule is broken. The rule and the shrinking condition depend on the question. The answer is the best window seen at any valid moment.

Take the list [3, 1, 2, 4, 1, 2, 5] and look for the longest stretch whose total is at most 8. Walk through it one right value at a time. The total of each window is shown after the shrink step.

The best window is 1, 2, 4, 1, with length 4, starting at index 1. The window never looked back at earlier values, and it never tested a stretch twice.

Why the left edge only moves forward

A reader will ask why this is safe. The left edge moves only forward, so the program never revisits a start position. That works here because every value is zero or more. When all values are non-negative, adding a value to a window never makes its total smaller. So if a window is too big, a window that starts at the same place and ends further right is also too big. Once the left edge has passed a start position, there is no need to go back to it.

This is the rule that the mistakes section breaks by using a negative value. Keep the rule in mind: the method in this lesson needs non-negative values.

Why shrinking uses while

When the window breaks the rule, one removal may not be enough. Take the window 1, 2, 4, 1, 2 in the table above. Its total is 10. Removing the first value leaves 9, which is still too big. The left edge has to keep moving until the total fits. So the shrink step is a while loop, which repeats while the condition holds. An if removes only one value, and the window stays broken. The mistakes section shows what that does to the answer.

What the best answer means

There are two kinds of question, and each one records the best answer at a different moment.

For the longest valid window, record the window after the shrink step, when it is valid. A longer valid window is better, so keep the largest length.

For the shortest window that reaches a target, the valid moment comes before the shrink. The window reaches the target, so it is valid. Record its length, then shrink, to test whether a shorter one also reaches the target. Keep the smallest length.

Worked example 1: the longest window with a total at most a limit

This program reads a limit and a list, then prints the length and values of the longest stretch whose total is at most the limit. It is the table above, written as a program.

The input has two numbers on the first line: n and the limit. The second line holds the n values. Save the program as main.py. Run it with python3 main.py, then type 7 8 and press Enter. Then type 3 1 2 4 1 2 5 and press Enter.

n, limit = map(int, input().split())
a = [int(x) for x in input().split()]
 
left = 0          # first index of the window
total = 0         # sum of a[left] through a[right]
best_length = 0
best_start = 0
 
for right in range(n):
    total += a[right]              # grow: take the new value on the right
 
    while total > limit:          # shrink until the window fits again
        total -= a[left]
        left += 1
 
    length = right - left + 1
    if length > best_length:
        best_length = length
        best_start = left
 
if best_length == 0:
    print("no subarray fits")
else:
    window = a[best_start:best_start + best_length]
    print(f"longest length {best_length} at index {best_start}: {window}")

Output:

longest length 4 at index 1: [1, 2, 4, 1]

Trace the three lines that matter. The line total += a[right] grows the window. The while loop shrinks it until the total is no more than the limit. The line length = right - left + 1 counts the values from left to right, including both ends. The + 1 is needed because the count of the values between two indexes is one more than their difference. For indexes 1 and 4, the window holds 4 values, and 4 - 1 is 3, so the + 1 makes the length right.

The condition length > best_length uses a strict comparison. On a tie, the first window found is kept. This matches the rule in the fixed-size lesson.

Python integers do not overflow, so the total stays exact however large the values grow. Other languages need a wider type for the total when values are large.

A detail to notice: if a single value is larger than the limit, the while loop removes every value in the window. Then left is one past right, so length is 0 and nothing is recorded. The program needs no special case for that.

The slice a[best_start:best_start + best_length] copies the window out of the list. The end index is not included, so the slice holds exactly best_length values.

Worked example 2: the shortest window with a total at least a target

This program reads a target and a list, then prints the length of the shortest stretch whose total reaches the target. The values are positive here. The shrink step runs while the window still reaches the target, and records the length each time, because each record is a valid window.

Type 8 15 and press Enter. Then type 1 2 3 4 5 6 7 8 and press Enter.

n, target = map(int, input().split())
a = [int(x) for x in input().split()]
 
left = 0
total = 0
shortest = None      # stays None if nothing reaches the target
 
for right in range(n):
    total += a[right]
 
    # The window reaches the target, so it is valid. Try to make it shorter.
    while total >= target:
        length = right - left + 1
        if shortest is None or length < shortest:
            shortest = length
        total -= a[left]
        left += 1
 
if shortest is None:
    print(f"no subarray reaches {target}")
else:
    print(f"shortest length {shortest}")

Output:

shortest length 2

Follow the window at two key moments. When right reaches the value 5, the window is 1, 2, 3, 4, 5, with total 15. That is valid, so the length 5 is recorded. The left edge then moves past the 1, and the total falls to 14, which stops the shrink loop.

At the last step, right reaches 8 and the window is 6, 7, 8, with total 21. The shrink loop records length 3, then removes 6. The total is 15, which still reaches the target, so the loop records length 2 for 7, 8, then removes 7. The total drops to 8 and the loop stops. The shortest length is 2.

Each record is a stretch that reaches the target. Later records can only be shorter, and the program keeps the smallest.

The program prints no subarray reaches 15 when nothing qualifies. Save the program and run it with 3 100, then 1 2 3. The output is no subarray reaches 100.

The value None stands for "not found", and the final check compares against it with is None. The mistakes section shows what happens when that check is missing. A value like this that marks "not found" is called a sentinel, and None is the clearest choice. Some programmers use float("inf") instead, which works because every real length is smaller than infinity.

Worked example 3: the longest substring with at most K distinct letters

The windows so far worked on numbers. The same method works on text. This example reads a word and a number k, then finds the longest piece of the word that uses no more than k different letters.

The window needs to know which letters it holds and how many of each. A dict stores that. A dict keeps pairs of a key and a value, here a letter and its count inside the window. The number of keys in the dict is the number of different letters in the window, which the program reads with len(counts).

Two lines do the work. counts[ch] = counts.get(ch, 0) + 1 adds 1 to the count of the letter ch, or starts it at 1 if the letter is not yet in the dict. When a letter's count drops to 0 while shrinking, the program deletes that key, so len(counts) counts only letters still in the window.

Type eceba and press Enter. Then type 2 and press Enter.

s = input()
k = int(input())
 
counts = {}
left = 0
best_length = 0
best_start = 0
 
for right, ch in enumerate(s):
    counts[ch] = counts.get(ch, 0) + 1          # grow on the right
 
    # Shrink from the left while there are too many different letters.
    while len(counts) > k:
        out = s[left]
        remaining = counts[out] - 1
        if remaining == 0:
            del counts[out]                     # the letter is gone from the window
        else:
            counts[out] = remaining
        left += 1
 
    length = right - left + 1
    if length > best_length:
        best_length = length
        best_start = left
 
print(best_length, s[best_start:best_start + best_length])

Output:

3 ece

The word eceba has the longest stretch ece, which has two letters, e and c, and length 3. Longer stretches such as ceb have three letters, so they are not allowed.

Try a longer input to see the same method scale. Type aabacbebebe and press Enter, then 3 and press Enter. The output is 7 cbebebe, which uses the three letters c, b and e.

Compare this with the number example. The grow step is the dict update. The shrink step is the while loop. The rule is "at most K different letters", and the check is len(counts) > k. Changing the question changes only the rule and the check. The rest of the method stays the same.

The enumerate(s) loop gives both the position right and the character ch on each pass. The standard library's collections.Counter is a dict built for counts, and it can replace the grow line. Keep the del, though: a Counter keeps a key whose count drops to 0, and len would count that key.

Common mistakes

Shrinking with if instead of while

A common first draft shrinks one time per step, using if. For the shortest-with-a-target question, one removal can leave the window still valid, and the program then misses a shorter answer.

Here is the shortest-window program with if in place of while, run on the list [1, 1, 1, 2] with target 2.

Output:

shortest length 2

The correct answer is 1, because the last value, 2, reaches the target by itself. At right equal to 3, the window is 1, 2 with total 3. The if version records length 2, then removes one value. That leaves 2 alone, with total 2, which is valid, but the loop does not check it again until the next step, and there is no next step. With while, the loop keeps removing while the total still reaches the target, so it records the length 1 window.

Negative values break the shrink rule

The shrink rule in this lesson assumes every value is zero or more. With a negative value, a bigger window can have a smaller total, and a valid stretch can hide behind a broken one. Here is the shortest-window program from worked example 2, run on the input 3 5 and then 1 -2 5.

no subarray reaches 5

The correct answer is 1, because the single value 5 reaches the target. The program never tests it. The left edge only moves when a window reaches the target, and the window with left edge at index 0 never reaches 5, because its totals are 1, then -1, then 4. So the left edge stays at index 0, and the window that starts at index 2 is never built.

For positive values, the method in this lesson is right. For values that can be negative, use a different method, such as prefix sums with a dict and a search for earlier prefix values. This lesson does not cover that method. Check the values before choosing the method.

Forgetting to remove a letter with a count of zero

In the letter example, the dict size is the number of different letters. If the program lowers a count to 0 and leaves the key in the dict, the size never drops. The shrink loop then keeps moving left past the window's right edge. Here is the example with the deletion removed, so the key stays:

s = "eceba"
k = 2
counts = {}
left = 0
for right in range(len(s)):
    ch = s[right]
    counts[ch] = counts.get(ch, 0) + 1
    while len(counts) > k:
        out = s[left]
        counts[out] = counts[out] - 1   # wrong: the key with count 0 stays
        left += 1
print(counts)

This program stops with an error before it prints:

Traceback (most recent call last):
  File "main.py", line 10, in <module>
    counts[out] = counts[out] - 1   # wrong: the key with count 0 stays
                  ~~~~~~^^^^^
KeyError: 'a'

The error means the loop reached the letter a, which the window has not yet added, because right is still at index 3. The dict has no key a, so reading it fails. The fix is the del when the count reaches 0, as in worked example 3.

Printing the sentinel when nothing qualifies

The shortest-window program uses None to mean "not found". If the final check is removed, the program prints that value as if it were a length. Take worked example 2, start shortest at float("inf") instead of None, delete the if check, and run it with the target 100 and the values 3 1 2.

Output:

shortest length inf

The sentinel float("inf") printed as inf, which is not a length. Always check for the sentinel before printing the answer, as worked example 2 does.

Counting the length without the plus one

The length of a window from index left to index right is right - left + 1. A common error is to write right - left, which is one short. The window 1, 2, 4, 1 from indexes 1 to 4 has length 4, and right - left gives 3. The program would then report a shorter answer than the true one, and the bug is quiet, because the program still prints a valid-looking window.

Practice

Exercise 1: longest window with a limit

Find the longest run of values in [1, 2, 1, 1, 3] whose total is at most 5. Give its length and its starting index.

Show the answer

The run 1, 2, 1, 1 starts at index 0, has total 5, and has length 4. No run of length 5 fits, because the whole list totals 8. The answer is length 4 at index 0.

Exercise 2: shortest window with a target

Find the length of the shortest run of values in [2, 3, 1, 2, 4, 3] whose total is at least 7.

Show the answer

Check the runs of length 1 first. No single value reaches 7. The runs of length 2 are 2, 3, 3, 1, 1, 2, 2, 4 and 4, 3. Their totals are 5, 4, 3, 6 and 7. The run 4, 3 reaches 7, so the answer is 2.

Exercise 3: at most one letter

Find the longest piece of the word aaabbc that uses at most one different letter. Give the piece and its length.

Show the answer

The piece aaa uses one letter and has length 3. The piece bb has length 2, and no piece with two letters is allowed. The answer is aaa, with length 3.

Exercise 4: why ties keep the first window

In worked example 1 the code uses length > best_length, not >=. Explain what changes if it used >=, and which window is reported for a limit where two windows have the same longest length.

Show the answer

With >=, a later window of the same length replaces the earlier one, so the program reports the last longest window it finds. With >, the first one found is kept. The length is the same either way. Only the reported start index can change. Write the rule down, because a question may ask for the first or the last answer.

Exercise 5: report the window itself

Change worked example 2 so it prints the values of the shortest window as well as its length. Describe the variables you need to add.

Show the answer

Keep two more variables, best_start and best_end, which hold left and right at the moment a shorter window is found. After the loop, print the values with a[best_start:best_end + 1]. The end index of a slice is not included, so add 1 to best_end to keep the last value.

Summary

• A variable-size window grows on the right for every value and shrinks on the left while the rule is broken.
• Each edge moves forward, so one pass over the list costs O(n).
• Use while for the shrink step, because one removal may not be enough to fix the window.
• For the longest valid window, record after shrinking. For the shortest window that reaches a target, record before shrinking.
• The method assumes non-negative values. Check the values before you rely on it.
• For letters, a dict of counts and its length give the number of different letters in the window.