Valid Anagram: Frequency Counting Pattern

Valid Anagram is one of the easiest problems on LeetCode, but it teaches you a building block that carries way more weight than the problem itself. The frequency counter pattern shows up in string matching, sliding windows, grouping problems, and more. If you have already solved Contains Duplicate and Two Sum, this is a great next step.

Let's break it down.

The problem

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

An anagram is a word formed by rearranging the letters of another word, using all the original letters exactly once.

Example: s = "anagram", t = "nagaram". The answer is True because both strings contain the same characters at the same frequencies.

And here is a case where the answer is False:

The question boils down to: do these two strings have the exact same character frequencies?

Approach 1: Sort and compare

The simplest approach. If two strings are anagrams, sorting both will produce the same result. "anagram" sorted is "aaagmnr". "nagaram" sorted is also "aaagmnr". Just compare.

def is_anagram(s: str, t: str) -> bool:
    return sorted(s) == sorted(t)

That is literally one line. It is clean, easy to remember, and correct. But sorting has a cost.

Time: O(n log n) where n is the length of the strings. Sorting dominates.

Space: O(n) because sorted() creates new lists.

For a problem this simple, O(n log n) is fine. LeetCode will accept it. But can we do better?

Approach 2: Frequency counting (optimal)

Instead of sorting, count how many times each character appears in both strings, then compare the counts. If every character has the same frequency in both strings, they are anagrams.

This is the frequency counter pattern. You build a dictionary (or array) of counts, and then check if the two dictionaries match.

def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False

    count = {}
    for ch in s:
        count[ch] = count.get(ch, 0) + 1
    for ch in t:
        count[ch] = count.get(ch, 0) - 1

    return all(v == 0 for v in count.values())

Let's walk through what each part does:

• Length check. If the strings have different lengths, they cannot be anagrams. This is a quick early exit that saves us from doing unnecessary work.
• Count up from s. Walk through s and increment the count for each character.
• Count down from t. Walk through t and decrement the count for each character. If t has the same characters at the same frequencies, every count ends up back at zero.
• Check all zeros. If any count is not zero, some character appeared more in one string than the other. Not an anagram.

One pass through each string. Each dictionary operation is O(1). Total time: O(n). Total space: O(1) since the alphabet is fixed at 26 lowercase English letters (the counts dictionary never grows beyond 26 entries).

Alternative: Counter one-liner

Python's Counter from the collections module makes this even shorter:

from collections import Counter

def is_anagram(s: str, t: str) -> bool:
    return Counter(s) == Counter(t)

Same idea, less code. Counter(s) builds a frequency dictionary, and Python's == on dictionaries checks that all keys and values match. Both are valid in interviews, but the explicit version is better for showing your thought process.

Alternative: fixed-size array

Since the problem constrains input to lowercase English letters, you can use a fixed-size array of 26 integers instead of a dictionary:

def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False

    count = [0] * 26
    for ch in s:
        count[ord(ch) - ord('a')] += 1
    for ch in t:
        count[ord(ch) - ord('a')] -= 1

    return all(c == 0 for c in count)

Same logic, but with an array indexed by character position. This avoids hash collisions entirely and is slightly faster in practice. The tradeoff is that it only works when the character set is known and small. For Unicode strings or arbitrary characters, the dictionary version is more flexible.

Complexity comparison

*O(1) because the character set is bounded at 26 lowercase letters. If the input could contain arbitrary Unicode, space would be O(k) where k is the number of distinct characters.

The frequency counter wins on time. The sort approach wins on simplicity. Both are acceptable in interviews, but the frequency counter is what interviewers want to see you reach. It shows that you understand how to trade a data structure for a faster algorithm.

Edge cases to watch for

A few things that trip people up:

• Different lengths. Always check len(s) != len(t) first. If the lengths differ, they cannot be anagrams regardless of character content. This is a free O(1) check that avoids unnecessary counting.
• Empty strings. Two empty strings are anagrams of each other. The algorithm handles this correctly without special cases.
• Single characters. s = "a", t = "a" returns True. s = "a", t = "b" returns False. Works naturally.
• Unicode / uppercase. The basic problem only uses lowercase English letters. If the interviewer asks "what if the input includes uppercase?" you can either normalize with .lower() or expand your counting structure. This is a great follow-up to mention proactively.

The building blocks

This problem is built from one core building block that appears across many other problems:

Frequency counter

The act of walking through a collection and counting how many times each element appears. The template is:

count = {}
for item in collection:
    count[item] = count.get(item, 0) + 1

This micro-pattern is the backbone of:

• Valid Anagram: count characters in both strings, compare counts
• Top K Frequent Elements: count frequencies, then extract the k most common
• First Unique Character: count frequencies, then find the first with count 1
• Ransom Note: count available characters, then check if the ransom note's characters are a subset
• Sliding window problems: maintain a frequency map of the current window, incrementing when elements enter and decrementing when they leave

The frequency counter is one of the three core hash map patterns (alongside complement lookup and grouping). If you read the Hash Map Patterns post, this is Pattern 1 in action. Valid Anagram is the simplest standalone example of it.

The key insight is that counting transforms a comparison problem ("are these two things equivalent?") into an equality check on a data structure. Instead of searching or sorting, you just build two frequency tables and compare them. Or, even better, build one table by counting up and counting down.

Problems that use the same bricks

Once you have the frequency counter down, try these:

• Group Anagrams: instead of comparing two strings, group a whole list of strings by their character frequencies. Uses the same counting technique as a hash map key.
• Top K Frequent Elements: frequency counter + bucket sort or heap to find the k most common elements
• First Unique Character in a String: frequency counter, then scan for count == 1
• Ransom Note: count the "magazine" characters, then verify the ransom note is a subset
• Minimum Window Substring: frequency counter inside a sliding window, one of the hardest applications of this pattern

Why you will forget this (and how to fix it)

Valid Anagram is so easy that it feels like there is nothing to forget. "Just count the characters and compare." But the building block here is not specific to anagrams. It is the frequency counter pattern itself, and you need that pattern to fire automatically when you encounter harder problems.

Three weeks from now, when you hit a sliding window problem that requires tracking character frequencies as elements enter and leave the window, you want the "count up, count down, check zeros" template to be in your fingers. Not something you have to re-derive from first principles.

Spaced repetition makes this stick. You practice typing the frequency counter template from scratch at increasing intervals. After a few cycles, the pattern is automatic. When a problem says "check if these two things have the same composition," you already know the approach before you finish reading the problem.

Related posts

• Hash Map Patterns - Valid Anagram is the simplest example of the frequency counting pattern, one of the three core hash map techniques
• Group Anagrams - The multi-string version of this problem, using frequency counting to generate hash map keys for grouping