Valid Anagram

Interview Prep

Warm-upArrays & Hashingstringscounting

The problem

Given two strings s and t, return True if t is an anagram of s — same characters in any order. Assume lowercase English letters.

Pattern: frequency comparison

Two strings are anagrams iff their multiset of characters is equal. The pattern: count each character on both sides and compare.

Solution 1 — sort and compare

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

O(n log n) time, O(n) space (for the sorted list). Cleanest possible code, fine answer in an interview if you flag the complexity.

Solution 2 — Counter

from collections import Counter

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

O(n) time, O(k) space where k is the alphabet size. Cleaner than rolling your own dict. Whether Counter equality counts as "doing it yourself" depends on the interviewer; usually fine.

Solution 3 — fixed 26-int array

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

O(n) time, O(1) space (the array is fixed-size). Single pass with one increment and one decrement per character — at the end every bucket is zero iff the strings agree. The version that scales to "do it without any high-level data structures."

Edge cases

Related