Valid Anagram Solution

Problem

Given two strings, determine whether one is a rearrangement of the other — using every character exactly once. Order doesn't matter; character counts do.

Example: s = "anagram", t = "nagaram" → true, because rearranging the letters of "anagram" yields "nagaram" exactly. Counter-example: s = "rat", t = "car" → false, because t contains a 'c' that s doesn't, and s contains a 't' that t doesn't.

Input: s = "anagram", t = "nagaram"
Output: true
Explanation: Both strings contain exactly three 'a's, one 'n', one 'g', one 'r', and one 'm'.

Intuition

Two strings are anagrams if and only if they have identical character frequencies. Sorting both strings brings all characters into the same canonical order, making equality trivial to check — but you pay O(n log n). The faster insight is that you only need to verify frequencies directly: count each character in s, then cancel those counts against t. If any count goes negative, t has a surplus of some character that s doesn't, and they can't be anagrams.

Approach 1 — Sort

Sort both strings alphabetically to produce a canonical form. Two strings are anagrams if and only if their sorted representations are identical.

If the lengths differ, return false immediately.
Sort the characters of s.
Sort the characters of t.
Return whether the two sorted sequences are equal.

1def isAnagram(s: str, t: str) -> bool:
2    if len(s) != len(t):
3        return False
4    return sorted(s) == sorted(t)    # sorted() returns lists; == compares element-by-element

Time: O(n log n) — the sort step dominates for strings of length n.
Space: O(n) — sorted() in Python and toCharArray() in Java allocate arrays proportional to input size.

Approach 2 — Frequency Count

Count occurrences of each character in s, then subtract counts as you scan t. An immediate negative means t uses more of that character than s ever had.

If the lengths differ, return false immediately.
Initialize a frequency array of 26 slots, one per lowercase letter.
Increment the slot for each character in s.
For each character in t, decrement its slot; if any slot drops below zero, return false.
Return true — all 26 counts balanced out.

1def isAnagram(s: str, t: str) -> bool:
2    if len(s) != len(t):
3        return False
4    frequency = [0] * 26
5    for char in s:
6        frequency[ord(char) - ord('a')] += 1
7    for char in t:
8        frequency[ord(char) - ord('a')] -= 1
9        if frequency[ord(char) - ord('a')] < 0:    # t has more of this char than s
10            return False
11    return True

Time: O(n) — two linear passes over strings of length n.
Space: O(1) — the frequency array is always exactly 26 integers, regardless of input size.

Complexity Summary

Approach	Time	Space	When to use
Sort	O(n log n)	O(n)	When brevity matters and n is small
Frequency Count	O(n)	O(1)	Default choice; optimal for large inputs

Common Mistakes

Skipping the length check — if len(s) != len(t), no arrangement of characters can make them equal; catching this first avoids any wasted iteration.
Decrementing all of t before checking — building a separate frequency map for t and comparing at the end works, but checking immediately when a count goes negative lets you return early on the first mismatch.
Assuming sorted() is free in Python — sorted(s) allocates a new list of size n; it's O(n) space, not O(1).
Forgetting the Unicode follow-up — the 26-slot array only works for lowercase ASCII. For arbitrary Unicode, use a hash map (Counter(s) == Counter(t)) which is O(k) space where k is the number of distinct characters.
Sorting a Java String directly — strings in Java are immutable; Arrays.sort requires a char[], so toCharArray() is mandatory before sorting.

Valid Anagram — Solution