Valid Anagram
easyTime: O(n)Space: O(1)
The shape of the problem
Return true iff string t is a permutation of string s. Different lengths are an immediate false.
Signals to notice
character frequency matchsame length requiredorder-independent comparison
Brute force first
Sort both strings and compare. O(n log n) time. Easy to write but slower than necessary.
The key insight
Anagrams have identical multisets of characters. Representing a multiset as a count map reduces equality-of-multisets to "every count is zero after balancing".
Trace it on s="anagram", t="nagaram"
lengths equal → proceed +s: a:1 n:1 a:2 g:1 r:1 a:3 m:1 -t: n:0 a:2 g:0 a:1 r:0 a:0 m:0 all counts 0 → return true
What must stay true
At every step, `count[c]` equals the number of times c has appeared in s so far minus the number of times in t so far.
Shape of the loop
if len(s) != len(t): return false
count = {}
for c in s: count[c] += 1
for c in t: count[c] -= 1
return all(v == 0 for v in count.values())Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Skipping the length check. Two strings can have identical counts only if they are the same length, but without the early return you waste allocations on obviously-different inputs.