Frequency Tracking While Scanning a Sequence

Frequency tracking keeps counts synchronized while the algorithm’s view of the data changes—subarrays, subtrees, or paths—often with enter/leave events.

Why this shows up in the real world

IDE reference counts for symbols; GC tracing sometimes tracks per-type allocation histograms online.

Core idea (explained for students)

Use incremental updates: add on enter scope, subtract on exit (backtracking) or slide window left border. Assert invariants sum(freq)==window_size when applicable.

Try this in Python

from collections import Counter


def freq_subarrays(s: str, k: int) -> list[Counter]:
    out = []
    c: Counter[str] = Counter()
    for i, ch in enumerate(s):
        c[ch] += 1
        if i >= k:
            old = s[i - k]
            c[old] -= 1
            if c[old] == 0:
                del c[old]
        if i >= k - 1:
            out.append(c.copy())
    return out


print([dict(x) for x in freq_subarrays('aabc', 2)])

Common mistakes

• Double counting when merging overlapping ranges.
• Recursive DFS forgetting to undo frequency change on backtrack.

Key takeaways

• Wrap mutations in try/finally rarely needed in CP; instead mirror add/remove symmetrically.
• Log freq snapshot on small tests.