Valid Anagram · DSA Prep

Two strings are anagrams exactly when they contain the same letters the same number of times. That’s a statement about counts, not order, so the fastest way to check it avoids arranging the letters at all — it just tallies them.

Sort and Compare

Time O(n log n)Space O(n)

If s and t are anagrams, sorting both produces identical strings. If they aren’t, sorting won’t magically make them equal.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)

Correct and simple, but sorted() allocates new lists and costs O(n log n) — more work than the comparison actually requires, since it also implicitly checks length equality and character multiplicity together.

Character Counting

OptimalTime O(n)Space O(1)

Count every character in s into a hash map, then walk t decrementing those same counts. If a character in t isn’t in the map, or a count ever goes negative, they can’t be anagrams. If every count lands back at zero, they are.

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

        counts = {}
        for ch in s:
            counts[ch] = counts.get(ch, 0) + 1

        for ch in t:
            if ch not in counts:
                return False
            counts[ch] -= 1
            if counts[ch] == 0:
                del counts[ch]

        return len(counts) == 0

Tracing s = "cat", t = "tac" — first the counting pass over s:

Hash Map

c → 1

1 / 6

resultcurrent

Count c in s. c now has count 1.

Correctness: the map after the first pass records exactly how many of each character s needs. The second pass spends those counts one by one; if t ever asks for a character that isn’t available, the strings aren’t anagrams. Since len(s) == len(t) is checked up front, ending with every count spent to zero proves the multisets match exactly.

Complexity: two linear passes over strings of length n — O(n) time. With lowercase English letters the map holds at most 26 entries — O(1) space (for the Unicode follow-up, the map would instead hold up to n distinct code points, making space O(n) — the algorithm itself needs no other change since a hash map works for any hashable character set).