Hashing strings

Use character frequency counters to check anagrams, group anagrams with a sorted-tuple key, and understand Python's O(n) string hashing cost.

Hashing turns a string into a compact key so that lookups, membership tests, and grouping become O(1) per query (amortised). The catch: building the hash value in the first place requires reading the entire string, so the initial cost is O(n). Understanding that distinction prevents subtle performance mistakes.

Character frequency as a fingerprint

Two strings are anagrams if and only if they contain exactly the same characters in the same quantities. A Counter (frequency map) captures this perfectly.

Python — editable, runs in your browser

from collections import Counter, defaultdict

# ── 1. Anagram check ──────────────────────────────────────────────────────────

def is_anagram(s, t):
  """True if s and t are anagrams of each other."""
  return Counter(s) == Counter(t)

# ── 2. Group anagrams ─────────────────────────────────────────────────────────
# Anagrams share the same sorted character tuple.
# Use that tuple as a dict key to cluster them together.

def group_anagrams(strs):
  groups = defaultdict(list)
  for s in strs:
      key = tuple(sorted(s))   # e.g. "eat" → ('a','e','t')
      groups[key].append(s)
  return list(groups.values())

# ── 3. Timing note — O(n) string hashing ─────────────────────────────────────
# Python caches the hash of a str object after the first call,
# so repeated hash(s) is O(1). But the *first* hash computation reads
# every character — O(n). Building a set of n strings of length m costs
# O(n * m) in hashing alone.
#
# Demonstrate: hashing short vs long strings
import timeit

short = "abc" * 10
long_s  = "abc" * 1000

t_short = timeit.timeit(lambda: hash(short + "x"), number=50000)
t_long  = timeit.timeit(lambda: hash(long_s  + "x"), number=50000)

print("Hash 30-char string, 50k times:", round(t_short * 1000, 1), "ms")
print("Hash 3000-char string, 50k times:", round(t_long * 1000, 1), "ms")

# ── Demo ──────────────────────────────────────────────────────────────────────
print()
print("is_anagram('anagram','nagaram'):", is_anagram("anagram", "nagaram"))  # True
print("is_anagram('rat','car'):", is_anagram("rat", "car"))                  # False

words = ["eat", "tea", "tan", "ate", "nat", "bat"]
print()
print("group_anagrams:", group_anagrams(words))

Why `tuple(sorted(s))` works as a key

Sorting a string produces its characters in alphabetical order. Any two anagrams produce the same sorted sequence. Wrapping it in a tuple makes it hashable so it can be used as a dict key. The cost per word of length m is O(m log m) for sorting.

An alternative is a frozen Counter: frozenset(Counter(s).items()). This is also O(m) but slightly more verbose.

Python interns (caches) the hash of str objects, so if you put a string into a set or dict and then look it up again, the second lookup does not re-hash. But string concatenation (s + t) produces a new object whose hash has not been computed yet, so it always pays the O(n) cost. Be careful when building keys by concatenation inside tight loops.

Where to go next

Next: lab — string problems — three exercises combining sliding window, two-pointer, and hashing: character replacement, palindrome checking on raw input, and finding all anagram positions.

Finished reading? Mark it complete to track your progress.

Character frequency as a fingerprint

Why tuple(sorted(s)) works as a key

Where to go next

On this page

Why `tuple(sorted(s))` works as a key