Valid Anagram

Problem

Given two strings s and t, return true if they are anagrams of each other, otherwise return false. Two strings are anagrams if they contain the same characters, each appearing the same number of times, in any order.

Example 1

Input:  s = "racecar", t = "carrace"
Output: true

Example 2

Input:  s = "jar", t = "jam"
Output: false

Example 3

Input:  s = "x", t = "x"
Output: true

Constraints

1 <= len(s), len(t) <= 5 * 10^4
s and t consist of lowercase English letters.

Thinking

Brute force idea: sort both strings and compare → $O(n \log n)$ . Correct, but sorting does more work than needed: we only care how many of each letter, not their order.
Key insight: two strings are anagrams ⇔ they have the same character counts. Counting is a single $O(n)$ pass. And since there are only 26 lowercase letters, the counts fit in a fixed-size array → $O(1)$ extra space.
Quick reject: if len(s) != len(t), they can’t be anagrams.
Edge cases to remember: different lengths, same letters but different counts ("aab" vs "abb"), single character, identical strings.

Solution

Approach A — my first solution (sort and compare)

Complexity: Time $O(n \log n)$ · Space $O(n)$ (sorted builds a new list of characters)

Short and correct. The cost is the sort: it puts every character in order, which is more than the question needs.

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

Approach B — `Counter` (Pythonic)

collections.Counter builds a dict of character → count; two Counters are equal when every count matches.

Complexity: Time $O(n)$ · Space $O(k)$ , where $k$ is the number of distinct characters (≤ 26 here). Works for any characters, including Unicode.

from collections import Counter

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

Approach C — fixed array of 26 counts ✅ best practice (what interviewers expect)

Add 1 for each letter of s, subtract 1 for each letter of t. They’re anagrams if every count ends at 0. ord(c) - ord('a') maps 'a'..'z' to 0..25.

Complexity: Time $O(n)$ · Space $O(1)$ (always 26 integers, no matter how long the strings are).

def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    count = [0] * 26
    for a, b in zip(s, t):
        count[ord(a) - ord("a")] += 1
        count[ord(b) - ord("a")] -= 1
    return all(c == 0 for c in count)

Scratch / Experiments

Timing at the maximum input size ( $5 \cdot 10^4$ characters).

Big-O isn’t the whole story in Python: sorted and Counter do their work in C, while Approach C’s loop runs in Python, so C can be slower in wall-clock time even though it’s the better algorithm. In an interview, C is the answer to explain; in real Python code, Counter is the idiomatic choice.

import random, string

s = "".join(random.choices(string.ascii_lowercase, k=50_000))
t = "".join(random.sample(s, len(s)))  # a shuffled copy, so it's an anagram
%timeit is_anagram_sort(s, t)
%timeit is_anagram_counter(s, t)
%timeit is_anagram(s, t)

Takeaways

Pattern: “same elements, any order” → compare frequency counts instead of sorting. Small fixed alphabet (e.g. 26 lowercase letters) → use an array of size 26 for $O(1)$ space; otherwise use a dict / Counter.
Mistakes I made: reached for sorting, which is $O(n \log n)$ , when counting is $O(n)$ . Also skipped the cheap len(s) != len(t) early exit.
Related problems: Contains Duplicate (#217, hash set), Group Anagrams (#49, use the sorted string or a 26-count tuple as a dict key), Find All Anagrams in a String (#438, sliding window + counts), Ransom Note (#383, counts).