Valid Anagram

Valid Anagram asks a simple question with a tidy trick behind it: do two strings use the exact same letters the same number of times? It is the perfect place to practice counting with a hash map.

The idea

Two strings are anagrams exactly when their letter counts match. So count how many of each letter s has, then go through t and subtract one for every letter you see.

If t is a true anagram, every tally lands back on zero. If t has a letter s does not (or too many of one), a tally drops below zero and we can stop early — they are not anagrams.

A quick first check: if the two strings are different lengths, they cannot be anagrams, so we return false immediately.

The alternative is to sort both strings and compare them. That works and is short, but sorting is O(n log n). Counting is O(n) — one pass to count, one pass to subtract.

Walk through it

Step through the animation. First we tally every letter of s = "anagram" into the count map. Then the pointer i scans t = "nagaram" left to right, subtracting one from a letter's tally at each stop. Watch the numbers tick down. When the scan finishes, every tally is 0 — so t is an anagram.

Pseudocode

if length of s is not equal to length of t:
    return false                  # different sizes can't be anagrams
 
make an empty map "count"
for each letter c in s:
    count[c] = count[c] + 1       # tally up the letters of s
 
for each letter c in t:
    count[c] = count[c] - 1       # subtract the letters of t
    if count[c] < 0:
        return false              # t has more of c than s does
 
return true                       # every tally landed on zero

The counting up and counting down are mirror images. A clean finish (no tally below zero, and equal lengths) means the books balance.

The Python solution

def is_anagram(s, t):
    if len(s) != len(t):
        return False
    count = Counter(s)
    for ch in t:
        count[ch] -= 1
        if count[ch] < 0:
            return False
    return True

• The length guard on line 2 is a cheap early exit — unequal lengths can never be anagrams.
• Counter(s) builds a dictionary of letter → how many times it appears in one pass. (from collections import Counter.)
• We then loop over t and do count[ch] -= 1 for each letter. A Counter returns 0 for a missing key, so subtracting makes it go negative — which line 7 catches.
• If we get through all of t without any tally going negative and the lengths matched, the counts are identical, so we return True.

Complexity

Time is O(n) — we touch each character a constant number of times. Space is O(1) because the map holds at most one entry per distinct letter, and the alphabet is a fixed size (26 for lowercase English). If the input can be any Unicode character, treat the space as O(k) for k distinct characters.

When this pattern shows up

Practice