Group Anagrams Patterns — Sort Key, Frequency Vector, and Prime Hash

Problem and Topic Statement#

Anagrams are strings that contain the same multiset of characters in different orders, like listen and silent. The interview family that revolves around this idea includes:

1. Group Anagrams (LC 49) — bucket an array of strings so all anagrams sit together.
2. Valid Anagram (LC 242) — confirm two strings are anagrams of each other.
3. Find All Anagrams in a String (LC 438) — return all start indices where s contains an anagram of p.
4. Permutation in String (LC 567) — does s2 contain any permutation of s1?

Each problem reduces to a single algorithmic question — how to fingerprint a multiset of characters cheaply. The choice of fingerprint determines whether the solution runs in O(nk log k), O(nk), or sliding-window O(n+k). This blog covers all three classical encodings and the windowed extensions used at Meta and Google.

Why This Topic Matters#

Anagram problems appear in roughly one in five string interviews because they probe two skills at once. First, the candidate must pick a representation — sorted key, frequency vector, or product hash — that is both correct and efficient. Second, the candidate must reason about the trade-off between hashing cost, memory, and clarity. Choosing wrong forces rewrites mid-interview, which signals the interviewer you have not internalised the pattern.

Group Anagrams (LC 49) is among the top fifty most-asked Meta problems. It is short enough to write in fifteen minutes yet rich enough to ask follow-ups: How would you parallelise it? What if strings contained Unicode? What if the alphabet were unknown size?

Find All Anagrams in a String (LC 438) is a Google favourite because it merges the anagram fingerprint with the sliding-window template — both fundamental string algorithm tools. Mastering it gives you a single template that solves at least eight other LeetCode problems including longest substring without repeating characters, minimum window substring, and substring with concatenation of all words.

Anagram fingerprints also appear in production code: deduplicating tag bags, matching scrambled hash outputs in Bloom-filter-like systems, comparing word-bag features in NLP, and even in DNA k-mer analysis where the bag of bases identifies a sequence's composition class. Knowing how to choose between encodings is a working-engineer skill, not just an interview trick.

The Core Insight#

Two strings are anagrams iff their character histograms are equal. Equality of histograms can be tested in three different ways, each producing a different time-space profile.

Sorting key. Sort the characters of each string and use the result as a dictionary key. Two anagrams sort to the same canonical form, e.g. eat, tea, ate all become aet. This is O(k log k) per string but trivial to implement correctly. It also handles arbitrary alphabets including Unicode without modification.

Frequency vector. For a fixed-size alphabet (typically 26 lowercase letters) compute the count of each character and use the tuple of counts as the key. This is O(k) per string. The key is a length-26 vector of ints; in Python you can use tuple(counts) directly. This is faster than sorting for moderate string lengths and the canonical FAANG answer.

Prime hash. Map each letter to a unique prime (a to 2, b to 3, c to 5, and so on). The product of the primes for the characters in the string is a unique number — by the fundamental theorem of arithmetic, two strings produce the same product iff they have the same multiset of characters. This is O(k) and produces a single integer key, but overflow is a real risk for long strings; use big integers or modular hashing.

For windowed problems like LC 438, the frequency vector wins because it allows O(1) updates as the window slides. Increment the entering character, decrement the leaving character, and compare to the pattern's vector. The comparison itself is O(26), still constant in alphabet size. Total work: O(n + k).

Visual Dry Run / Worked Example#

Example 1 — Group Anagrams. strs = ["eat", "tea", "tan", "ate", "nat", "bat"].

Using sorted-key encoding:

Output: [["eat","tea","ate"], ["tan","nat"], ["bat"]].

Using frequency-vector encoding the keys are (1,0,0,0,1,0,...,1,...) style tuples but the grouping is identical.

Example 2 — Find All Anagrams. s = "cbaebabacd", p = "abc".

Build pattern vector pf = [1, 1, 1, 0, ..., 0]. Initialise window wf with first three characters of s (cba): wf = [1, 1, 1, 0, ..., 0]. They match, so index 0 is an answer.

Slide one step right. Window becomes bae. Decrement c, increment e: wf = [1, 1, 0, 0, 1, ...]. Mismatch.

Continue. At index 6 the window is bac, vectors match again. At index 7 it is acd, mismatch. Final answer: [0, 6].

Each step is O(1) update plus O(26) compare. Total O(n).

Solution (Optimal)#

Group Anagrams — Frequency Vector (Python)#

from collections import defaultdict
 
def groupAnagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        counts = [0] * 26
        for ch in s:
            counts[ord(ch) - ord('a')] += 1
        groups[tuple(counts)].append(s)
    return list(groups.values())

Group Anagrams — Frequency Vector (JavaScript)#

function groupAnagrams(strs) {
  const groups = new Map();
  for (const s of strs) {
    const counts = new Array(26).fill(0);
    for (const ch of s) counts[ch.charCodeAt(0) - 97]++;
    const key = counts.join(',');
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(s);
  }
  return Array.from(groups.values());
}

Time complexity: O(nk) where n is the number of strings and k their average length. Space: O(nk) for the output.

Find All Anagrams — Sliding Window (Python)#

def findAnagrams(s, p):
    if len(p) > len(s):
        return []
    pf = [0] * 26
    wf = [0] * 26
    for ch in p:
        pf[ord(ch) - ord('a')] += 1
    res = []
    k = len(p)
    for i, ch in enumerate(s):
        wf[ord(ch) - ord('a')] += 1
        if i >= k:
            wf[ord(s[i - k]) - ord('a')] -= 1
        if wf == pf:
            res.append(i - k + 1)
    return res

Find All Anagrams — Sliding Window (JavaScript)#

function findAnagrams(s, p) {
  if (p.length > s.length) return [];
  const pf = new Array(26).fill(0);
  const wf = new Array(26).fill(0);
  for (const ch of p) pf[ch.charCodeAt(0) - 97]++;
  const k = p.length;
  const res = [];
  const eq = (a, b) => a.every((v, i) => v === b[i]);
  for (let i = 0; i < s.length; i++) {
    wf[s.charCodeAt(i) - 97]++;
    if (i >= k) wf[s.charCodeAt(i - k) - 97]--;
    if (i >= k - 1 && eq(wf, pf)) res.push(i - k + 1);
  }
  return res;
}

Time: O(n) with a 26-cell compare per shift. Space: O(1) extra.

Common Mistakes#

• Using Python's sorted(s) directly as a dict key. sorted returns a list, which is unhashable; convert to tuple or string first.
• Forgetting that frequency vectors only work cleanly for known alphabets. For Unicode strings prefer Counter or sorted keys.
• Comparing two 26-cell vectors with == inside an n-iteration loop and forgetting that this is O(26) — usually fine, but if you blow up the alphabet to 256 or more, batch updates with a matches counter as in classic minimum-window-substring solutions.
• Off-by-one in the sliding window. The shrink step happens when i >= k, not i > k. Test on tiny inputs.
• Using product-of-primes without big integers in languages with fixed-width integers — overflow silently corrupts the key.
• Returning the dictionary itself instead of dict.values() in Group Anagrams.

Interview Tips#

State both options — sorted key and frequency vector — early. Mention that sorted is simpler but slower, then commit to frequency vector for the optimal solution. This shows you weighed alternatives.

Discuss the alphabet. Ask whether the input is lowercase ASCII or Unicode. The answer determines whether you can use a 26-int vector or need a HashMap.

Pre-emptively state that two equal frequency vectors guarantee anagram equivalence — interviewers love this kind of justification because it shows you understand correctness.

When coding the windowed variant, draw the window as a literal box around three characters of the example string. Updating it visually proves you understand the entering and leaving character mechanics.

Mention the prime-hash trick as a curiosity. It impresses but you should not propose it as the primary solution because of overflow.

Finish by mentioning Counter from Python's collections. It compares equal when histograms match, making the solution one line: Counter(s1) == Counter(s2) for valid anagram. Interviewers like this because it shows fluency with the standard library.

Follow-up Questions#

What if the alphabet is unknown and very large, like Unicode? Switch to a hash map of code-point counts. Group Anagrams becomes a tuple(sorted(counter.items())) key, which is O(k log k) due to sorting the unique characters but still correct.

What if memory is constrained? The 26-int vector is constant memory per string. The sorted-key approach allocates k characters per key. For millions of strings the vector approach uses roughly half the memory.

Find All Anagrams with k different characters allowed. Generalise to longest substring with at most k character mismatches. Use a matches counter that tracks how many alphabet positions currently equal the pattern; only when matches == 26 is the window an anagram. This gives O(n) overall, even with large alphabets.

Streaming version. Numbers arrive one character at a time. Maintain the rolling window's frequency vector and emit each match as it occurs. This is the same as LC 438 but with input as a generator.

Anagrams over a binary alphabet. With only two characters, the anagram condition reduces to "same number of zeros". A single integer counter suffices. This shows up in interview variants involving DNA or boolean strings.

Key Takeaways#

• Anagram detection reduces to comparing character histograms; pick the encoding that fits your alphabet and update model.
• Sorted-key encoding is the easiest to write and works for any alphabet but costs O(k log k) per string.
• Frequency-vector encoding is O(k) per string and supports O(1) sliding-window updates — the FAANG-preferred choice.
• Prime-product encoding compresses the key to a single integer but risks overflow on long strings; use big integers if you go that route.
• Find All Anagrams and Permutation in String are sliding-window applications of the same fingerprint, achieving O(n + k) total work.
• These problems appear constantly at Meta, Google, Amazon, and most string-heavy interviews; mastering the three encodings unlocks dozens of LeetCode variants.