Anagram Pattern

Before we start

"Anagram" sounds like a word puzzle, but it is really a disguised frequency-comparison problem. By the end of this chapter you will be able to:

• Check if two strings are anagrams in three ways (sorted, Counter, array) and know which to choose when.
• Find all anagram windows inside a longer string in O(n) — the sliding window variant.
• Connect this to Chapter 3.2's sliding window: anagram detection is just the fixed-size window with a frequency equality check.

Picture this first (no code yet)

The actual problem

Valid Anagram (LC #242):

Given two strings s and t, return True if t is an anagram of s.

"anagram" and "nagaram" → True   (same letters, rearranged)
"rat"     and "car"     → False  ('r','a','t' vs 'c','a','r' — different stock)

Simple to state. Three ways to solve it — and each teaches something different.

First, the slow way (so you feel the pain)

Generate every permutation of s and check if any matches t. For a string of length 10, there are 10! = 3 628 800 permutations. For length 20: 2.4 quintillion. The universe will end before you finish checking n = 20. We can do this in O(n log n) with sorting, or O(n) with frequency counting.

The turning point

The one idea to remember

Three ways to check: side-by-side

Method 1 — Sort both strings

def isAnagram_sort(s: str, t: str) -> bool:
    return sorted(s) == sorted(t)   # O(n log n)

Simplest code. But O(n log n) and allocates new sorted lists.

Method 2 — Counter comparison

from collections import Counter

def isAnagram_counter(s: str, t: str) -> bool:
    return Counter(s) == Counter(t)   # O(n)

O(n) time and space. Pythonic. Counter(s) == Counter(t) compares dictionaries — O(k) where k is distinct characters.

Method 3 — 26-element frequency array

def isAnagram_array(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    freq = [0] * 26
    for c in s: freq[ord(c) - ord('a')] += 1
    for c in t: freq[ord(c) - ord('a')] -= 1
    return all(x == 0 for x in freq)

O(n) time, O(1) space (26-element array is constant). Best choice when you need minimum memory, or in languages without built-in Counter.

When to choose which:

Watch it happen, frame by frame (frequency array method)

s = "anagram", t = "nagaram"

Build freq from s:
  a: +1 → 3 times total
  n: +1
  g: +1
  r: +1
  m: +1
freq after s = [3,0,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,0,0]
               (a=3, g=1, m=1, n=1, r=1)

Subtract freq from t:
  n: -1, a: -1, g: -1, a: -1, r: -1, a: -1, m: -1
freq after t = [0,0,0,0,0,0,0,...] — all zeros

all(x == 0) → True  ✅

The sliding window variant: Find All Anagrams (LC #438)

Now the problem is: given a long string s and a short pattern p, find all starting indices in s where a substring of length len(p) is an anagram of p.

s = "cbaebabacd",  p = "abc"
Output: [0, 6]
s[0:3] = "cba" — anagram of "abc" ✅
s[6:9] = "bac" — anagram of "abc" ✅

Brute force: for each of n - m + 1 windows, check anagram in O(m) — total O(n × m). For n=100 000 and m=100, that is 10 million checks. We can do O(n) with a sliding frequency map.

The O(n) sliding approach

from collections import Counter

def findAnagrams(s: str, p: str) -> list[int]:
    k      = len(p)
    if k > len(s):
        return []

    need   = Counter(p)          # required frequency for each char in p
    have   = Counter(s[:k])      # frequency of first window
    result = []

    if have == need:
        result.append(0)

    for i in range(k, len(s)):
        # add incoming character on the right
        have[s[i]] += 1

        # remove outgoing character on the left
        old = s[i - k]
        have[old] -= 1
        if have[old] == 0:
            del have[old]          # keep dict clean for correct == comparison

        if have == need:
            result.append(i - k + 1)

    return result

Frame-by-frame: s = "cbaebabacd", p = "abc" (k=3)

need = {a:1, b:1, c:1}

First window s[0:3] = "cba":
have = {c:1, b:1, a:1} == need → result = [0]

i=3, add 'e', remove s[0]='c':
have = {b:1, a:1, e:1}  ≠  need

i=4, add 'b', remove s[1]='b':
have = {a:1, e:1, b:1}  ≠  need

i=5, add 'a', remove s[2]='a':
have = {e:1, b:1, a:1}  ≠  need

i=6, add 'b', remove s[3]='e':
have = {b:2, a:1}  ≠  need

i=7, add 'a', remove s[4]='b':
have = {b:1, a:2}  ≠  need

i=8, add 'c', remove s[5]='a':
have = {b:1, a:1, c:1} == need → result = [0, 6]

i=9, add 'd', remove s[6]='b':
have = {a:1, c:1, d:1}  ≠  need

Answer: [0, 6]  ✅

One pass through s. Each character is added once and removed once — O(n) total.

Variant: Group Anagrams (LC #49)

Covered in Chapter 2.7 (Custom Hash Design). Key technique: canonical key = "".join(sorted(word)). All anagrams map to the same sorted string → same bucket in the dictionary.

Where to spot this pattern

Trigger words:

• "anagram" or "permutation of"
• "rearrangement" where order doesn't matter
• "contains all characters of" — if order doesn't matter, it's anagram; if order matters, it's subsequence (Chapter 3.1)
• "find all occurrences of any permutation of p in s" — always sliding anagram window

5 disguises:

1. Valid Anagram (LC #242): direct frequency comparison.
2. Find All Anagrams in a String (LC #438): sliding fixed window + Counter equality.
3. Permutation in String (LC #567): "does s2 contain a permutation of s1?" — same sliding window, return True on first match.
4. Group Anagrams (LC #49): canonical key (sorted string or freq tuple) → group into buckets.
5. Minimum Window Substring (LC #76): looks like anagram but the window is variable size and must contain all chars of t (not equal count) — different pattern (Chapter 3.2).

Common traps

Complexity

N = number of words, k = average word length.

# O(n log n): sorted(s) == sorted(t)
# O(n):       Counter(s) == Counter(t)
# O(n), O(1): 26-array — add for s, subtract for t, check all zeros

need = Counter(p);  have = Counter(s[:k])
if have == need: result.append(0)
for i in range(k, len(s)):
    have[s[i]] += 1
    old = s[i-k]; have[old] -= 1
    if have[old] == 0: del have[old]   # ← critical!
    if have == need: result.append(i-k+1)

Check yourself

Practice problems

Next up: Trie-based String Problems — the prefix tree data structure that answers "does any word in a dictionary start with this prefix?" in O(L) time, and how it powers autocomplete, word search, and longest common prefix.