Faangprep Logo
Log inStart free
Browse curriculum

Valid Anagram

Decide whether two strings are anagrams by counting letters in a hash map.

EasySolve on LeetCode

Problem Understanding

Valid Anagram: given two strings s and t, return true if t is an anagram of s — the same letters, each used the same number of times, in any order.

Examples: s = "anagram", t = "nagaram" is true. s = "rat", t = "car" is false.

Attempt 1: Sort Both Strings

Sort the letters of both strings and compare: anagrams sort to the same string. It is correct and short, but sorting costs O(n log n) time. The question underneath — does every letter appear the same number of times in both? — can be answered by counting, without ordering anything.

The Intuition: Count, Then Spend

A hash map from letter to count turns the question into bookkeeping:

  1. If the lengths differ, return false immediately.
  2. Walk s and add one to each letter's count.
  3. Walk t and spend one count per letter. If a letter's count is already 0, t has more of that letter than s — return false.

If t finishes without running out of anything, the strings are anagrams. The length check is what makes that last step safe: equal lengths and nothing overspent means every count ended at exactly 0.

Interactive Walkthrough

s = "anagram", t = "nagaram"

LENGTHS MATCH

s

a

0

n

1

a

2

g

3

r

4

a

5

m

6

t

n

0

a

1

g

2

a

3

r

4

a

5

m

6

Answer

—

count (letter:count)

Empty

 

Both strings have 7 letters. Start an empty count

Next

s[0] = 'a': count['a'] is now 1

s

t

Both strings are drawn as rows. The first pass walks s while the count map beside the figure grows; the second walks t while the counts fall and matched letters grey out. A letter of t that finds its count at 0 ends the run.

The approach, step by step

  1. Compare lengths

    If s and t have different lengths, return false.

  2. Count s

    Add one to the count of each letter of s.

  3. Spend on t

    For each letter of t, return false if its count is 0; otherwise subtract one. Return true at the end.

Frequently asked questions

How do you check if two strings are anagrams?

If the lengths differ they are not. Otherwise count each letter of s in a hash map, then walk t and spend one count per letter; if any letter of t finds its count at 0, they are not anagrams. If t finishes, they are.

Why not sort both strings and compare them?

Sorting works and is short to write, but it costs O(n log n) time. Counting letters is O(n) time with O(k) extra space for k distinct letters — O(1) when the alphabet is fixed, such as 26 lowercase letters.

Why check the lengths first?

Strings of different lengths can never be anagrams, so the check returns early. It also makes the final step valid: with equal lengths, if no letter of t ever runs out, every count must end at exactly 0.