← Pointer Manipulation

Micro-Drill #92 — Window with counter

Pointer Manipulation Target: 15s

Counter-based window matching powers minimum-window-substring and anagram problems.

from collections import Counter
need = Counter(t)
have, required = 0, len(need)
left = 0
for right in range(len(s)):
    c = s[right]
    need[c] -= 1
    if need[c] == 0: have += 1
    while have == required:
        # record window [left, right]
        need[s[left]] += 1
        if need[s[left]] > 0: have -= 1
        left += 1

Type it from memory. Go.

Practice Problems

Related Coding Drills

← Micro #91 Micro #93 →