Write a function to check whether two strings are anagrams of each other. What is the optimal time complexity?

How to think about it

This is a frequency-counting problem wearing a string costume. Two strings are anagrams if and only if they hold exactly the same characters with exactly the same counts — and once you say it that way, the code almost writes itself. What the interviewer is really watching for is whether you reach for the O(n) frequency count rather than stopping at the obvious sort, and whether you remember the edge cases: case and spaces.

The first-pass answer is the sort, and it’s fine to name out loud:

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

Two strings with identical character frequencies sort to the same sequence, so the comparison holds. The follow-up, though, is always “can you beat O(n log n)?” — and you can, by counting instead of sorting.

A worked example

Counter builds a frequency map in a single pass; two Counters are equal exactly when every character has the same count in both. A length check up front turns the most common rejection into O(1), and a quick normalisation handles real-world inputs:

from collections import Counter

def is_anagram(s: str, t: str) -> bool:
    """O(n) anagram check via character-frequency counts."""
    if len(s) != len(t):              # cheap early exit
        return False
    return Counter(s) == Counter(t)

def is_anagram_normalised(s: str, t: str) -> bool:
    """Case-insensitive, space-ignoring version."""
    clean = lambda x: x.replace(" ", "").lower()
    return Counter(clean(s)) == Counter(clean(t))

print(is_anagram("listen", "silent"))                      # True
print(is_anagram("hello", "world"))                        # False
print(is_anagram("abc", "ab"))                             # False (length check fires)

print(is_anagram_normalised("Astronomer", "Moon starer"))  # True
print(is_anagram_normalised("The eyes", "They see"))       # True

print("Counter('listen'):", Counter("listen"))
print("Counter('silent'):", Counter("silent"))

True
False
False
True
True
Counter('listen'): Counter({'l': 1, 'i': 1, 's': 1, 't': 1, 'e': 1, 'n': 1})
Counter('silent'): Counter({'s': 1, 'i': 1, 'l': 1, 'e': 1, 'n': 1, 't': 1})

The two Counters print in different orders — Counter keeps first-seen order — yet they compare equal, because equality is about counts, not arrangement. That’s exactly the anagram property: same characters, same counts, any order.

Why Counter beats sort

Counter is O(n) time and O(k) space, where k is the number of distinct characters — at most 26 for lowercase letters, so effectively constant space on a fixed alphabet. Sorting builds a whole new sorted sequence: O(n log n) time and O(n) extra space. For a fixed alphabet you can push further still and use a 26-slot array, shaving the constant factor.