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.

Checking if two words are anagrams means verifying they contain the exact same characters in the exact same quantities, just arranged differently. The goal is to determine if one string is simply a scrambled version of the other.

Sorting (O(N log N))

If we sort the characters in both strings, two anagrams will become identical. We can then compare the sorted results directly to see if the "ingredients" match.

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

The sorting approach is slow because it rearranges data when we only need to compare frequencies. The core insight is that an anagram is just a character inventory. If we count how many times each letter appears in both strings, the inventories must match perfectly.

Tally Sheet (O(N))

We use a fixed-size array (26 for lowercase English) to track the balance of characters.
- For every character in s, we increment its slot in the array.
- For every character in t, we decrement its slot.
If all slots end at zero, the strings are anagrams.

python
if len(s) != len(t): return False
counts = [0] * 26
for i in range(len(s)):
    counts[ord(s[i]) - ord('a')] += 1
    counts[ord(t[i]) - ord('a')] -= 1

return all(x == 0 for x in counts)
Worked Example:s = "rat", t = "car"
0
r
s[i]
1
a
2
t
We examine the first characters: we add 1 to the count of 'r' and subtract 1 from the count of 'c'.
0
r
1
a
s[i]
2
t
We examine the second characters: we add 1 to the count of 'a' and subtract 1 from the count of 'a', leaving its balance at 0.
0
r
1
a
2
t
s[i]
We examine the third characters: we add 1 to the count of 't' and subtract 1 from the count of 'r'.
0
c
1
a
2
r
During inventory verification, we find that 'c' has a non-zero balance of -1, meaning the strings are not anagrams.
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