Fixed-size windows and matching

When the width never changes, the window becomes a rolling comparison against a target.

Key idea

One in, one out

When the window width is fixed, there is no shrink loop. Every step adds exactly one element on the right and removes exactly one on the left, so the state update is two operations regardless of how wide the window is.

That is what makes fixed windows cheap. Recomputing from scratch would cost the window width per step; rolling costs a constant.

1def vowels_in_each_window(text, width):2    """How many vowels sit in each window of the given width."""3    vowels = set("aeiou")4    counts = []5    inside = 06 7    for right in range(len(text)):8        if text[right] in vowels:9            inside += 110        if right >= width:                       # something leaves11            if text[right - width] in vowels:12                inside -= 113        if right >= width - 1:                   # window is full14            counts.append(inside)15 16    return counts17 18print(vowels_in_each_window("abciou", 3))

Why it works

Tracking how many letters already agree

Instead of comparing whole maps, keep a single number: how many distinct characters currently have exactly the right count. When that number equals the number of distinct characters in the target, the window matches.

Update it whenever a count changes. If a count just became equal to its target, the number goes up. If it just moved away from equal, the number goes down. The subtlety is that a single change can only affect the one character whose count changed, so the update is constant time.

1def windows_with_exactly_two_vowels(text, width):2    """Start indexes of windows holding exactly two vowels."""3    vowels = set("aeiou")4    starts = []5    inside = 06 7    for right in range(len(text)):8        if text[right] in vowels:9            inside += 110        if right >= width:11            if text[right - width] in vowels:12                inside -= 113        if right >= width - 1 and inside == 2:14            starts.append(right - width + 1)15 16    return starts17 18print(windows_with_exactly_two_vowels("abciou", 3))

What the problem below needs

The problem asks whether any window of a fixed width matches a target exactly, where exactly means the same characters with the same counts. You know how to roll a fixed window, you know how to build a count map, and you know from Unit 1 that two count maps compare equal when their contents agree. Put those together.

Code lab· 20 min

Rolling comparisons

averages_of_width returns the average of every window of the given width, rolling the total rather than resumming. first_window_with_all_distinct returns the start index of the first window of the given width whose characters are all distinct, or -1. matches_target_counts reports whether a window of text starting at start has exactly the character counts given in target.

solution.py

Tests

print(averages_of_width([1, 2, 3, 4], 2))print(first_window_with_all_distinct("abcabc", 3), first_window_with_all_distinct("aaaa", 2))print(matches_target_counts("abcb", 1, {"b": 2, "c": 1}), matches_target_counts("abcb", 0, {"b": 2, "c": 1}))

Output

Run tests to see output.

Problem· 22 min

Permutation In String

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 vowels_in_each_window(text, width):2 """How many vowels sit in each window of the given width."""3 vowels = set("aeiou")4 counts = []5 inside = 06 7 for right in range(len(text)):8 if text[right] in vowels:9 inside += 110 if right >= width: # something leaves11 if text[right - width] in vowels:12 inside -= 113 if right >= width - 1: # window is full14 counts.append(inside)15 16 return counts17 18print(vowels_in_each_window("abciou", 3))

1def windows_with_exactly_two_vowels(text, width):2 """Start indexes of windows holding exactly two vowels."""3 vowels = set("aeiou")4 starts = []5 inside = 06 7 for right in range(len(text)):8 if text[right] in vowels:9 inside += 110 if right >= width:11 if text[right - width] in vowels:12 inside -= 113 if right >= width - 1 and inside == 2:14 starts.append(right - width + 1)15 16 return starts17 18print(windows_with_exactly_two_vowels("abciou", 3))

What the problem below needs

print(averages_of_width([1, 2, 3, 4], 2))print(first_window_with_all_distinct("abcabc", 3), first_window_with_all_distinct("aaaa", 2))print(matches_target_counts("abcb", 1, {"b": 2, "c": 1}), matches_target_counts("abcb", 0, {"b": 2, "c": 1}))