LeetCode Valid Anagram: Counting Characters in O(n)

LeetCode 242, Valid Anagram, is officially an Easy problem, but it is a perfect early stop on the path to mastering string and hashing patterns. Interviewers love it because it tests whether you reach for sorting reflexively or whether you can spot the linear counting solution. In this walkthrough we cover both approaches, the complexity tradeoffs, the edge cases that catch candidates off guard, and a clean interview explanation.

The Problem

Given two strings s and t, return true if t is an anagram of s, and false otherwise. An anagram is a rearrangement of the same characters, so the two strings must contain the same multiset of letters.

Example 1:

• Input: s = "anagram", t = "nagaram"
• Output: true

Example 2:

• Input: s = "rat", t = "car"
• Output: false

The classic constraint says the strings contain only lowercase English letters, but the follow-up asks how you would handle Unicode characters.

Brute Force

The easiest correct solution is to sort both strings and compare them.

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

This works because two anagrams produce the same sorted sequence. Time complexity is O(n log n) because of the sort, and space is O(n) for the sorted copies in Python. It is short and readable, which makes it a fine baseline in an interview, but we can do better.

Optimal Solution

Counting characters is linear. If the alphabet is fixed and small, an array of size 26 is the most efficient structure.

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

    counts = [0] * 26
    for ch in s:
        counts[ord(ch) - ord('a')] += 1
    for ch in t:
        counts[ord(ch) - ord('a')] -= 1
        if counts[ord(ch) - ord('a')] < 0:
            return False
    return True

We walk s and increment the bucket for each character, then walk t and decrement. If any bucket ever drops below zero, t contains a letter that s does not have enough of, and we can stop early. If we finish without that happening and the lengths match, every bucket is zero.

For the Unicode follow-up, swap the array for a hash map:

from collections import Counter

def isAnagram(s: str, t: str) -> bool:
    return len(s) == len(t) and Counter(s) == Counter(t)

Counter is implemented with a hash map, so this still runs in linear time but allocates entries only for characters that appear.

Walk Through an Example

Take s = "anagram" and t = "nagaram". After scanning s, counts holds three a’s, one n, one g, one r, and one m. Scanning t, the first n drops n to zero, the next a drops a from three to two, then g, a, r, a, m. Every decrement keeps the bucket non-negative, and the final array is all zeros, so we return true.

Now take s = "rat" and t = "car". After s we have one r, one a, one t. Walking t, the first c decrements c from zero to negative one, and we return false immediately. The early termination is a small but useful optimization.

Edge Cases

• Different lengths: handled by the length check up front. Without it you would still need to compare totals at the end.
• Empty strings: two empty strings are anagrams by definition, and the loops do nothing, so we return true.
• Case sensitivity: the problem treats A and a as different. If a follow-up changes that, normalize with s.lower() before counting.
• Whitespace and punctuation: the standard problem assumes none, but real anagram puzzles often ignore them. Strip them out before counting.
• Unicode: a fixed array of 26 will not work. Use a hash map or Counter.

Complexity Analysis

Both optimal versions run in O(n) time, where n is the length of either string. The array version uses O(1) extra space because the array is always size 26. The Counter version uses O(k) extra space, where k is the number of distinct characters. The sorting baseline is O(n log n) time and O(n) space. If you are new to these notations, our refresher on Big O notation walks through the reasoning.

How to Explain It in an Interview

• Restate the problem and confirm the alphabet: lowercase English only, or full Unicode.
• Mention sorting as the obvious baseline at O(n log n).
• Pivot to counting: walk s, increment buckets, walk t, decrement, and check for any negative.
• Justify the O(1) space claim by pointing to the fixed 26-letter alphabet.
• Offer the Counter variant as your answer to the Unicode follow-up.

This sequence shows that you can produce a working solution quickly and then refine it without being prompted.

Related Problems

• LeetCode 49, Group Anagrams, which extends this counting idea across many strings.
• LeetCode 383, Ransom Note, which is the same character-count check in disguise.
• LeetCode 438, Find All Anagrams in a String, which combines this with a sliding window.

For more context on the underlying tools, revisit strings introduction and operations and hashing and hash maps.

Wrap up

Valid Anagram is a tiny problem with a big lesson: when the alphabet is small, fixed-size counting beats sorting every time. The two-line sorted comparison is a fine first answer, but moving to a linear count and explaining why it is constant space is what turns a working solution into a strong interview signal. Practice both variants so you can switch to the hash map version the moment a follow-up question changes the constraints.