Stage 1 · Code

String Algorithms

String Hashing and Anagrams

Use polynomial hashes for fast substring comparison, and combine them with frequency signatures and grouping tricks for anagram-heavy interview problems.

18 min readData Structures & Algorithms in GoCode

Why String Comparison Becomes a Bottleneck

Many string problems are not hard because one comparison is hard. They are hard because the same style of comparison happens thousands of times. Checking whether two substrings are equal, whether many words belong to the same anagram group, or whether a sliding window matches a target multiset can turn into a bottleneck if every check scans characters from scratch.

Two common escape hatches are hashing and signatures. Hashing gives a compact, order-sensitive summary of a string or substring, which is useful when exact order matters. Anagram signatures deliberately ignore order and keep only counts or a canonical arrangement, which is useful when the task cares about the multiset of letters rather than their positions.

Need	Useful tool	Why
Fast equality of many substrings	Polynomial hash / prefix hash	Order matters and repeated comparisons should become O(1) after preprocessing
Check if two strings are anagrams	Frequency count or sorted canonical form	Order should be ignored
Group many words by anagram class	Frequency signature map	Equal signatures collapse into one bucket

Prefix Hashes for Substrings

A prefix hash lets you compute a polynomial hash for every prefix once, then recover any substring hash with subtraction. If H[i] is the hash of the first i characters and pow[i] stores powers of the base, then the hash of s[l:r] can be extracted from H[r] - H[l]*pow[r-l], all modulo the chosen prime. That turns repeated substring comparison into constant-time arithmetic after linear preprocessing.

Worked example on 'ababa'

Map a=1, b=2, base=5
Use H[i+1] = H[i]*5 + value(s[i])

H = [0, 1, 7, 36, 182, 911]
pow = [1, 5, 25, 125, 625, 3125]

Hash of s[0:3] = 'aba' = H[3] - H[0]*125 = 36
Hash of s[2:5] = 'aba' = H[5] - H[2]*125 = 911 - 7*125 = 36

Same normalized hash => same substring, assuming no collision

The subtraction peels away the contribution of the prefix before l, leaving only the weighted substring. Stored base powers line the positions back up correctly.

Comparing equal substrings inside 'ababa'

first 'aba'

aoverlaps second copy

asecond 'aba' ends here

Hash collisions still exist with prefix hashes

Prefix hashes make substring queries fast, not infallible. If the stakes are high, use double hashing or verify the final candidate substring before trusting equality.

Anagram Signatures

Anagrams ignore order, so a polynomial hash is often the wrong first tool because it intentionally distinguishes eat from tea. For anagram problems, the most reliable signature is usually a 26-length frequency vector for lowercase English letters. Two words are anagrams if and only if their frequency vectors are identical.

Sorting each word into canonical order also works: eat, tea, and ate all become aet. That is easy to explain, but costs O(k log k) for a word of length k. A frequency signature costs O(k) and avoids per-word sorting, which is why it is a popular optimization for grouping tasks.

Two ways to represent an anagram class

word  = 'listen'
word' = 'silent'

sorted canonical form:
- sort('listen') = 'eilnst'
- sort('silent') = 'eilnst'

frequency signature (conceptually):
- a:0 b:0 c:0 ... e:1 i:1 l:1 n:1 s:1 t:1
- identical counts => anagrams

Use the representation that matches the scale of the problem. Sorting is simpler; counting is usually faster.

Technique	Best for	Time per word / query	Trade-off
Sorted canonical string	Simple anagram grouping	O(k log k)	Easy to code, slower on long words
Frequency signature	Anagram checks and grouping	O(k)	Needs fixed alphabet or a map-based count structure
Polynomial hash	Ordered substring comparison	O(1) query after O(n) preprocessing	Collision handling required

Match the signature to the problem definition

If order matters, choose a hash or direct comparison. If order must be ignored, choose counts or a canonical sort. Many wrong solutions come from using the right tool for the wrong equivalence relation.

Go Implementation

This lesson needs two practical building blocks: a prefix-hash helper for substring comparison, and an anagram-grouping helper based on frequency signatures. Together they cover both order-sensitive and order-insensitive string reasoning without forcing one technique to solve every problem.

Goprefix-hashing-and-anagram-grouping-in-go.go

70 linesLn 1, Col 1Go

`Hash(l, r)` recovers a substring hash in O(1) after preprocessing. `groupAnagrams` uses a frequency-vector key because anagrams care about counts, not order. Together they illustrate two different notions of string equivalence.

Practice Problems

#242Valid AnagramEasyFrequency signature · O(n) time · O(1) space #49Group AnagramsMediumCanonical signature map · O(total characters) time · O(total characters) space #438Find All Anagrams in a StringMediumSliding window plus frequency signature · O(n) time · O(1) space #1044Longest Duplicate SubstringHardBinary search plus substring hashing · O(n log n) average time · O(n) space

Quiz

Quiz & Practice

Question 1 / 3

Why are prefix hashes useful?

Summary

Prefix hashes turn repeated substring-equality queries into O(1) operations after O(n) preprocessing.
Hashing is order-sensitive, which is perfect for substring comparison but wrong for anagram logic.
Anagram problems usually want sorted canonical forms or frequency signatures instead.
Collision awareness is part of understanding string hashing, not an optional footnote.
Strong solutions choose the signature that matches the problem's notion of equality instead of forcing one tool onto every task.

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.