Windows with Counts
24 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Some window rules count items: the same letters as a word, or at most k different letters. A Counter keeps those counts and changes in O(1) when the window moves.
Count what is inside the window
Frequency count is a table that says how many times each item appears. In Python, Counter(text) builds one as a dictionary-like object that returns 0 for items it has not seen.
Some rules depend on how many times each item appears, not on a sum. A Counter holds those counts. Comparing two Counters tells you whether two blocks have the same items.
from collections import Counter
word = "listen"print(Counter(word))print(Counter("listen") == Counter("silent"))Example 1 · Brute force: sort every window
s, p = "cbaebabacd", "abc"k = len(p)starts = [i for i in range(len(s) - k + 1) if sorted(s[i:i + k]) == sorted(p)]print(starts)[0, 6]
What this code does
- Two blocks are anagrams when their sorted letters are equal.
- Each window is sorted, so the cost is O(n * k log k).
Counters ignore the order of items. Building one for a block of k items costs O(k).
Update the counts as the window moves
Building a new Counter for every window repeats work. When the window slides, add one to the entering item and subtract one from the leaving item.
from collections import Counter
text = "abcab"k = 3window = Counter(text[:k])for right in range(k, len(text)): window[text[right]] += 1 old = text[right - k] window[old] -= 1 if window[old] == 0: del window[old] print(dict(window))Example 2 · Better: how many different letters are in each window
from collections import Counter
text = "aabca"k = 3window = Counter(text[:k])print(len(window))for right in range(k, len(text)): window[text[right]] += 1 old = text[right - k] window[old] -= 1 if window[old] == 0: del window[old] print(len(window))2 3 3
What this code does
- The windows are aab, abc and bca.
- Deleting zero counts keeps
len(window)equal to the number of different letters.
Delete a key when its count reaches zero. Then len(window) is the number of different items in the window.
Anagrams in a string
Anagram is a word or block that uses exactly the same letters as another, the same number of times, in any order. "listen" and "silent" are anagrams.
Find every place in s where a block of letters is an anagram of p. The window has the length of p, and its Counter must equal the Counter of p.
from collections import Counter
s, p = "cbaebabacd", "abc"need = Counter(p)window = Counter(s[:len(p) - 1])starts = []for right in range(len(p) - 1, len(s)): window[s[right]] += 1 if window == need: starts.append(right - len(p) + 1) old = s[right - len(p) + 1] window[old] -= 1 if window[old] == 0: del window[old]print(starts)Example 3 · Anagram starts with Counter comparison
from collections import Counter
def anagram_starts(s, p): need = Counter(p) window = Counter(s[:len(p) - 1]) starts = [] for right in range(len(p) - 1, len(s)): window[s[right]] += 1 if window == need: starts.append(right - len(p) + 1) old = s[right - len(p) + 1] window[old] -= 1 if window[old] == 0: del window[old] return starts
print(anagram_starts("abab", "ab"))print(anagram_starts("hello", "xyz"))print(anagram_starts("a", "ab"))[0, 1, 2] [] []
What this code does
- Overlapping anagrams are all found: "abab" has them at 0, 1 and 2.
- When p is longer than s, the loop does not run and the list stays empty.
Example 4 · Optimal: one number instead of a comparison
from collections import Counter
def anagram_starts(s, p): need = Counter(p) missing = len(p) starts = [] for right, ch in enumerate(s): if need[ch] > 0: missing -= 1 need[ch] -= 1 left = right - len(p) if left >= 0: old = s[left] need[old] += 1 if need[old] > 0: missing += 1 if missing == 0: starts.append(right - len(p) + 1) return starts
print(anagram_starts("cbaebabacd", "abc"))print(anagram_starts("abab", "ab"))[0, 6] [0, 1, 2]
What this code does
missingis updated in O(1), so no Counter comparison is needed.- Letters that enter and leave are balanced the same way, so the counts always describe the current window.
The new letter is added, the window is compared, and then the oldest letter is removed. Each comparison costs about the alphabet size, not the text length.
Minimum window substring
Minimum window substring is the shortest piece of a text s that contains every letter of another text t, counting repeated letters. It is a classic interview problem.
Find the shortest piece of s that holds every letter of t, with repeats. Track missing, the number of needed letters not yet covered. A letter we do not need goes below zero, which is fine.
from collections import Counter
need = Counter("ABC")missing = 3for ch in "ADOB": if need[ch] > 0: missing -= 1 need[ch] -= 1 print(ch, missing)Example 5 · Brute force: shortest piece that covers t
from collections import Counter
s, t = "ADOBECODEBANC", "ABC"best = ""for i in range(len(s)): for j in range(i + len(t), len(s) + 1): if not Counter(t) - Counter(s[i:j]): if best == "" or j - i < len(best): best = s[i:j] breakprint(best)BANC
What this code does
- Subtracting Counters keeps only the letters still missing. An empty result means the piece covers t.
- This tries every start and grows the end, so it is O(n^2) or slower.
Example 6 · Optimal: minimum window with missing
from collections import Counter
def min_window(s, t): need = Counter(t) missing = len(t) left = 0 best = (len(s) + 1, 0) for right, ch in enumerate(s): if need[ch] > 0: missing -= 1 need[ch] -= 1 while missing == 0: best = min(best, (right - left + 1, left)) need[s[left]] += 1 if need[s[left]] > 0: missing += 1 left += 1 size, start = best return s[start:start + size] if size <= len(s) else ""
print(min_window("ADOBECODEBANC", "ABC"))print(repr(min_window("a", "aa")))print(min_window("aa", "aa"))BANC '' aa
What this code does
- The window grows until
missingis 0, then shrinks while it is still complete. - The best result is a pair (length, start), and
minpicks the shorter length. - It is O(n + m) time, where m is the length of t.
Example 7 · Longest piece with at most k different letters
from collections import Counter
def longest_k_distinct(text, k): window = Counter() left = best = 0 for right, ch in enumerate(text): window[ch] += 1 while len(window) > k: window[text[left]] -= 1 if window[text[left]] == 0: del window[text[left]] left += 1 best = max(best, right - left + 1) return best
print(longest_k_distinct("eceba", 2))print(longest_k_distinct("aabacbebebe", 3))print(longest_k_distinct("aaaa", 1))3 7 4
What this code does
- This is a variable window whose rule is
len(window) <= k. - The shrink step needs the zero-count delete, otherwise len would never fall.
A letter only lowers missing while its count is still above zero. When missing is 0, the window holds everything, so record it and shrink from the left.
Next step
Check your understanding
11 quick questions