Frequency Signatures and Histogram Fingerprints

A frequency signature compresses a multiset into a canonical form—sorted tuple of (char, count) or count vectors—used to group anagrams or detect equivalence.

Why this shows up in the real world

Shingling in near-duplicate detection; checksum-style equivalence for curriculum items with same difficulty mix.

Core idea (explained for students)

Signature function must be pure and order-insensitive for multiset equality: sort keys or use fixed-length array tuple.

Try this in Python

from collections import Counter


def sig(s: str) -> tuple[tuple[str, int], ...]:
    return tuple(sorted(Counter(s).items()))


def group_anagrams(strs: list[str]) -> list[list[str]]:
    buckets: dict[tuple[tuple[str, int], ...], list[str]] = {}
    for w in strs:
        buckets.setdefault(sig(w), []).append(w)
    return list(buckets.values())


print(group_anagrams(['eat', 'tea', 'tan', 'ate']))

Common mistakes

• Including positions accidentally makes signatures too strict.
• Huge tuples when alphabet large—prefer hashing signatures with collision awareness.

Key takeaways

• tuple(sorted(Counter(s).items())) is readable for interviews.
• For performance, 26-length tuple of counts beats sorting pairs.