Hash Map for Frequency Counting

Hash map + frequency is the default pattern for “count characters”, “at most k distinct”, or balancing deletions—dict or Counter central to the state.

Why this shows up in the real world

Spam filters count tokens per sender; cache stores per-key hit counts for eviction policies.

Core idea (explained for students)

Keep cnt and sometimes valid derived flags. Sliding window: expand r, shrink l until constraint satisfied.

Try this in Python

from collections import Counter


def freq(s: str) -> Counter:
    return Counter(s)


print(freq('mississippi').most_common(3))

Common mistakes

• Removing key when count hits zero vs leaving zero entries—choose one style consistently.
• Unicode combining characters changing perceived length.

Key takeaways

• Counter subtraction c1-c2 keeps only positive counts— multiset difference.
• For “longest with k distinct” track len(cnt).