Algorithm

Valid Anagram

Arrays & Strings Pattern

Valid Anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise. An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

CONSTRAINTS
  • 1 <= s.length, t.length <= 5 × 10⁴
  • s and t consist of lowercase English letters
EXAMPLE 1
Input: s = "anagram", t = "nagaram"
Output: true
Both strings hold three a's and one each of n, g, r, m — identical letters in identical counts, only the order differs.
EXAMPLE 2
Input: s = "rat", t = "car"
Output: false
Both have length 3, but t contains a 'c' that s does not, and s contains a 't' that t does not, so neither is a rearrangement of the other.
EXAMPLE 3
Input: s = "a", t = "ab"
Output: false
Different lengths. A rearrangement uses exactly the same letters, so t cannot be an anagram of a shorter s.
Must the two strings be the same length?
Yes. An anagram uses every original letter exactly once, so strings of different lengths can never be anagrams — that is an immediate false before any counting.
Is the comparison case-sensitive, and which characters can appear?
Here the inputs are only lowercase English letters, so case never arises. If uppercase or Unicode were allowed, confirm the rules with the interviewer and likely switch from a 26-slot array to a hash map keyed by character.
Does t have to be a different string from s?
For this coding problem, identical strings satisfy the definition (every count matches), so s == t returns true. The 'different word' wording in the plain-English definition is not enforced by the return contract.
Is there a constraint on extra space?
A first solution may use whatever it needs, but note the counting solution already uses only constant extra space for a fixed alphabet.

Two strings are anagrams when one is a rearrangement of the other — the same letters, each used the same number of times, with only the order changed. "listen" and "silent" are anagrams; "rat" and "car" are not. We return a single boolean: true when t is a rearrangement of s, false otherwise. Two facts fall straight out of the definition and are worth stating before any code: if the two strings have different lengths they cannot possibly be anagrams, and the order of the letters never matters — only how many of each letter each string holds.

The honest first idea: sort both, then compare

If order does not matter, we can destroy the order on purpose. Sort the letters of each string, and two anagrams collapse to the very same sequence: both "rat" and "tar" become "art". So sort both strings and check whether the results are identical.

python
if len(s) != len(t):
    return False
return sorted(s) == sorted(t)

This is correct and only two lines. But sorting a string of N characters costs on the order of N log N comparisons — the log N factor is the price of fully ordering the letters. And that is more work than the question asked for. We never needed the letters in order; we only need to know that the two strings hold the same counts of each letter. Sorting pays for a total ordering when a plain tally would do. Where the sort spends N log N arranging letters, can we reach the same answer in one straight pass?

The reframe: an anagram is an inventory, not an arrangement

Stop thinking of a word as a sequence and start thinking of it as a census of letters: "anagram" is nothing more than {a: 3, n: 1, g: 1, r: 1, m: 1}. Two strings are anagrams if and only if their censuses are identical — three a's here must meet three a's there, and so on for every letter. This reframe is the whole solution: comparing two inventories needs no sorting at all, just counting, and counting is a single linear sweep.

Counting in a fixed 26-slot array

Because the strings are made only of the 26 lowercase English letters, we can hold the entire census in a fixed array of 26 integers — one slot per letter. To turn a character into a slot index we use its numeric code: ord('a') is the code for 'a', so ord(c) - ord('a') maps 'a' to 0, 'b' to 1, … 'z' to 25.

We could build one census for s and one for t and compare them. But there is a tidier one-array trick: walk both strings together, adding one for each letter of s and subtracting one for each letter of t in the same slots. If the two are anagrams, every letter is added exactly as many times as it is subtracted, so every slot returns to zero. Any surplus or deficit in any slot means some letter appears more often in one string than the other — not an anagram.

python
if len(s) != len(t):
    return False
counts = [0] * 26
for i in range(len(s)):            # equal length, so one loop covers both
    counts[ord(s[i]) - ord('a')] += 1
    counts[ord(t[i]) - ord('a')] -= 1
return all(x == 0 for x in counts)
Crucial Notethe length check on the first line is not merely an optimization — the single combined loop depends on it. The loop indexes both s and t with the same i, so it is only well-defined when the strings are the same length. And the check is needed for correctness, not speed: "ab" versus "abb" would otherwise never get its extra 'b' counted, because the loop stops at the shorter length. Rejecting unequal lengths up front removes that whole class of bug.
Worked Example:s = "rat", t = "car"
Same length (3), so we run the combined loop — +1 for each letter of s, -1 for each letter of t:
- i = 0: 'r' of s adds one to slot r; 'c' of t subtracts one from slot c. (r: +1, c: -1)
- i = 1: 'a' of s adds one; 'a' of t subtracts one — slot a nets back to 0.
- i = 2: 't' of s adds one; 'r' of t subtracts one. (t: +1, r: back to 0)
- Final slots: c = -1, t = +1, all others 0. Not all zero, so return false. The -1 in slot c says "t has a 'c' that s never supplied", and the +1 in slot t says the reverse — precisely why they are not anagrams.
What we paid, and what we bought

Counting makes one pass over the strings and one pass over 26 fixed slots, so the time is O(N) — we shed the log N factor the sort was paying. The extra memory is 26 integers no matter how long the strings grow: a constant, so O(1) space. The trade to remember: whenever a problem cares about "the same elements regardless of order", the reflex is to reach for a frequency count, not a sort — counting compares multisets directly and in linear time. That one reflex unlocks a whole family: grouping anagrams together, finding every anagram of a pattern inside a longer string (a sliding window over these same counts), and checking whether one string is a permutation of another. Sorting answers all of them too, but always one log N factor slower.

One caveat worth voicing in an interview: the 26-slot array only works because the alphabet is fixed and small. If the strings could contain Unicode — emoji, accented letters, any of a million code points — a 26-slot array collapses. The fix keeps the exact same counting idea but swaps the fixed array for a hash map keyed by character, trading the O(1) alphabet space for O(k) space in the number of distinct characters seen.

Interactive Strategy Visualization

Bucket Balancing

Frequency Reconciliation Engine
A
+1
N
A
G
R
A
M
Memory
WAITING FOR DATA...
N
A
G
A
R
A
M
📥

Processing input string. For every A, we increment the count.

O(N log N) Sorting
→
O(N) Time · O(1) Space Tally