AlgoMaster Logo

Valid Anagram

Last Updated: March 29, 2026

easy

Understanding the Problem

Two strings are anagrams if and only if they contain the exact same characters with the exact same frequencies. "listen" and "silent" are anagrams because both have one 'l', one 'i', one 's', one 't', one 'e', and one 'n'. But "hello" and "world" are not, because their character counts differ.

So the real question is: how do we efficiently check whether two strings have identical character frequency distributions? There are a few ways to think about it, from straightforward sorting to direct counting.

Key Constraints:

  • 1 <= s.length, t.length <= 5 * 10^4 → With n up to 50,000, O(n^2) would mean 2.5 billion operations, which is too slow. O(n log n) and O(n) are both fine.
  • s and t consist of lowercase English letters → Only 26 possible characters. This means a fixed-size array of length 26 is enough to count frequencies, no need for a hash map.

Approach 1: Sorting

Intuition

The simplest way to check if two strings are anagrams: sort both of them and compare. If the sorted versions are identical, the original strings must contain the same characters in the same quantities, just in a different order.

Think of it like this. If you have two bags of Scrabble tiles and you arrange each bag's tiles in alphabetical order, the two arrangements will be identical if and only if the bags contain the same tiles.

Algorithm

  1. If s and t have different lengths, return false immediately.
  2. Sort both strings alphabetically.
  3. Compare the sorted strings character by character.
  4. If they match, return true. Otherwise, return false.

Example Walkthrough

Input:

0
a
1
n
2
a
3
g
4
r
5
a
6
m
s
0
n
1
a
2
g
3
a
4
r
5
a
6
m
t

After sorting both strings:

0
a
1
a
2
a
3
g
4
m
5
n
6
r
sorted(s)
0
a
1
a
2
a
3
g
4
m
5
n
6
r
sorted(t)

Both sorted strings are identical, so we return true.

Code

Sorting works, but it establishes a full ordering of all characters when we only need to know if the frequencies match. What if we simply counted how many times each character appears?

Approach 2: Hash Map (Frequency Count)

Intuition

Instead of sorting, count the frequency of each character in both strings and compare. Two strings are anagrams if and only if every character appears the same number of times in both.

Since the problem guarantees only lowercase English letters (26 characters), we can use a fixed-size array instead of a hash map. Array access is faster than hash map lookups, and the space is constant.

Algorithm

  1. If s and t have different lengths, return false.
  2. Create a frequency array of size 26 (one slot per letter).
  3. For each character in s, increment the corresponding count.
  4. For each character in t, decrement the corresponding count.
  5. If any count is not zero, return false. Otherwise, return true.

Example Walkthrough

1i=0: s[0]='a' → count['a']++, t[0]='n' → count['n']--
0
a
i
1
n
2
a
3
g
4
r
5
a
6
m
1/6
1i=0: t[0]='n' → count['n']--
0
n
i
1
a
2
g
3
a
4
r
5
a
6
m
1/6
1i=0: count['a']++ → 1, count['n']-- → -1
a
:
1
n
:
-1
1/6

Code

This approach is already optimal in Big-O terms. But can we detect a mismatch during the counting phase itself, without the final verification loop?

Approach 3: Single Array with Early Exit

Intuition

Instead of using one combined loop, we first count characters in s, then iterate through t and decrement. If any count goes negative during the t pass, we know immediately that t has more of that character than s, so we can return false early without finishing.

This doesn't change the worst-case complexity, but in practice, non-anagram pairs are often caught within the first few characters.

Algorithm

  1. If s and t have different lengths, return false.
  2. Create a frequency array of size 26.
  3. Count all characters in s (increment counts).
  4. Iterate through t. For each character, decrement its count. If any count drops below zero, return false immediately.
  5. If the loop completes without returning false, return true.

Example Walkthrough

1Count all characters in s = "rat"
0
r
1
a
2
t
1/4
1Waiting to process t after counting s
0
c
1
a
2
r
1/4
1Counting s: r→1, a→1, t→1
r
:
1
a
:
1
t
:
1
1/4

Code