Skip to content
16-Week DSA Roadmap
LeetCode #242EasyProblem 2 of 8

Valid Anagram

Decide whether two words use exactly the same letters, the same number of times.

  • Frequency counting

Before this, know: Strings and indexes, Hash maps (Map in JavaScript, dict in Python)

The problem in plain English

You get two words, s and t. Return true if t is an anagram of s, and false otherwise.

An anagram is a word made by rearranging all the letters of another word, using each letter exactly once. “listen” and “silent” are anagrams. So are “anagram” and “nagaram”. “rat” and “car” are not: “rat” has a t, “car” has a c.

A string is a row of characters, so like an array each character has an index starting at 0:

s
  1. a0
  2. n1
  3. a2
  4. g3
  5. r4
  6. a5
  7. m6
t
  1. n0
  2. a1
  3. g2
  4. a3
  5. r4
  6. a5
  7. m6
Same letters, different order: a, n, a, g, r, a, m and n, a, g, a, r, a, m. Both have three a's, one g, one m, one n and one r.

The rules that matter:

  • Order doesn’t matter, counts do. “aab” and “abb” use the same kinds of letters but not the same amounts, so they’re not anagrams.
  • If the lengths differ, the answer is false straight away.
  • On LeetCode the words contain only lowercase English letters a to z (remember this, it unlocks a trick later), and can be up to 50,000 letters long.

Before you code: think it through

Those piles are a frequency count: for each letter, how many times it appears. We’ll store them in a hash map (a Map in JavaScript, a dict in Python): a structure that stores key → value pairs and finds any key in about one step. Here the key is a letter and the value is its count.

count5 items
lettercount
a3
n1
g1
r1
m1
The frequency count of 'anagram': letter → how many times it appears.

Pause and think

s = 'aab' and t = 'abb'. Both have length 3 and both use only a and b. Are they anagrams? What do the counts say?

Approach 1: Brute force

The most direct idea: for each letter of s, scan t for an unused copy of that letter and cross it off. If we can’t find one, they’re not anagrams. If every letter finds a partner, they are.

Brute force: cross letters off

s = "rat", t = "car"

s
  1. r0
  2. a1
  3. t2
letters of t still unused
  1. c0
  2. a1
  3. r2
variables
letters scanned
3
answer
—
  • Looking at now
  • Matching letter in t
  • Just crossed off
  • Crossed off earlier

s[0] is "r". Scan t's letters from the start: found an unused "r" at position 2. (3 letters looked at so far.)

Step 1 / 5

Which line is running?

function isAnagram(s, t) {  if (s.length !== t.length) return false;  const left = t.split(""); // letters of t we haven't used yet  for (const ch of s) {Running now:     const at = left.indexOf(ch); // scan for a matching letter    if (at === -1) return false;    left[at] = null; // cross it off so it can't be used twice  }  return true;}

Brute force: cross letters off

function isAnagram(s, t) {  if (s.length !== t.length) return false;  const left = t.split(""); // letters of t we haven't used yet  for (const ch of s) {    const at = left.indexOf(ch); // scan for a matching letter    if (at === -1) return false;    left[at] = null; // cross it off so it can't be used twice  }  return true;}
def is_anagram(s, t):    if len(s) != len(t):        return False    left = list(t)  # letters of t we haven't used yet    for ch in s:        if ch not in left:  # scan for a matching letter            return False  # no unused copy of ch is left        left[left.index(ch)] = None  # cross it off so it can't be used twice    return True

Crossing off matters: without it, “aab” vs “abb” would match the first a of t twice.

Why is it slow?

Each letter of s may scan most of t. With words of length n that’s up to n × n letter checks. For 7 letters, about 49. For 50,000 letters (LeetCode’s limit), about 2,500,000,000. We describe this growth with Big-O notation, a short way of saying how the work grows as the input grows (see Big-O in 5 minutes). Work that grows like n × n is O(n²): double the length and the work goes up four times.

A better idea: sort both

If we sort the letters of both words, anagrams turn into the exact same string: “anagram” and “nagaram” both become “aaagmnr”. Then one comparison answers the question.

Sort and compare

function isAnagram(s, t) {  if (s.length !== t.length) return false;  return [...s].sort().join("") === [...t].sort().join("");}
def is_anagram(s, t):    return sorted(s) == sorted(t)

Sorting costs about n × log n steps, written O(n log n). For 50,000 letters that’s under a million steps: a huge improvement, and a fine answer to give first in an interview. But we can do it in a single pass, with no sorting.

The pattern: frequency counting

Both slow approaches are really trying to answer “does each letter appear the same number of times?”. So let’s count directly.

Pattern

Frequency counting

Template

Use it when: the answer depends on how many times each value appears, not on the order.

Signal words

  • “anagram”
  • “same characters”
  • “permutation of”
  • “how many times”
  • “most frequent”
  • “majority”

Approach 2: Count with a hash map

  1. If the lengths differ, return false.
  2. Make an empty hash map count.
  3. Walk through s. For each letter, add 1 to its count.
  4. Walk through t. For each letter, if its count is 0 (or missing), t has a letter s can’t supply: return false. Otherwise subtract 1.
  5. If we get through all of t, return true.

Press Play and watch the counts go up while we walk s (violet) and back down while we walk t (amber). Then try “rat” vs “car” to see where it fails, and the two edge cases.

Count with a hash map

s = "anagram", t = "nagaram"

s
  1. a0
  2. n1
  3. a2
  4. g3
  5. r4
  6. a5
  7. m6
t
  1. n0
  2. a1
  3. g2
  4. a3
  5. r4
  6. a5
  7. m6
count0 items
lettercount
empty
variables
walking
—
answer
—
  • Looking at now
  • Already counted
  • Tally went up (from s)
  • Tally went down (used by t)
  • Letter t can't match

Both words have 7 letters, so they might be anagrams. Make an empty hash map "count": letter → how many of that letter s has given us.

Step 1 / 17

Which line is running?

function isAnagram(s, t) {  if (s.length !== t.length) return false;Running now:   const count = new Map(); // letter -> how many s has that t hasn't used up  for (const ch of s) {    count.set(ch, (count.get(ch) ?? 0) + 1);  }  for (const ch of t) {    if (!count.get(ch)) return false; // t has a letter s ran out of    count.set(ch, count.get(ch) - 1);  }  return true;}

Why is it safe to return true without checking that every count is 0 at the end? The lengths are equal, so t takes away exactly as many letters as s put in. If no count ever went below zero along the way, they must all have landed on exactly zero.

Approach 3: An array of 26 slots

LeetCode promises only lowercase a to z. That’s just 26 possible keys, so we can swap the hash map for a plain array of 26 counters. Slot 0 counts a, slot 1 counts b, …, slot 25 counts z.

To find a letter’s slot we use its character code, the number a computer uses to store it: 'a' is 97, 'b' is 98, and so on. So code − 97 gives 0 for a, 1 for b, 25 for z.

This version also walks both words at the same time: +1 for s[i], −1 for t[i]. Slots can dip below zero in the middle; only the final check matters.

Count with an array of 26 slots

s = "anagram", t = "nagaram"

s
  1. a0
  2. n1
  3. a2
  4. g3
  5. r4
  6. a5
  7. m6
t
  1. n0
  2. a1
  3. g2
  4. a3
  5. r4
  6. a5
  7. m6
count
  1. a00
  2. b01
  3. c02
  4. d03
  5. e04
  6. f05
  7. g06
  8. h07
  9. i08
  10. j09
  11. k010
  12. l011
  13. m012
  14. n013
  15. o014
  16. p015
  17. q016
  18. r017
  19. s018
  20. t019
  21. u020
  22. v021
  23. w022
  24. x023
  25. y024
  26. z025
variables
answer
—
  • Looking at now
  • +1 from s
  • −1 from t
  • Not zero at the end
  • Zero

Make 26 counters, all 0: one slot per letter, 'a' in slot 0 up to 'z' in slot 25. The slot number is the letter's code minus the code of 'a'.

Step 1 / 16

Which line is running?

function isAnagram(s, t) {  if (s.length !== t.length) return false;Running now:   const count = new Array(26).fill(0); // slot 0 = 'a' ... slot 25 = 'z'  for (let i = 0; i < s.length; i++) {    count[s.charCodeAt(i) - 97]++; // 97 is the character code of 'a'    count[t.charCodeAt(i) - 97]--;  }  return count.every((c) => c === 0);}

26 counters

function isAnagram(s, t) {  if (s.length !== t.length) return false;  const count = new Array(26).fill(0); // slot 0 = 'a' ... slot 25 = 'z'  for (let i = 0; i < s.length; i++) {    count[s.charCodeAt(i) - 97]++; // 97 is the character code of 'a'    count[t.charCodeAt(i) - 97]--;  }  return count.every((c) => c === 0);}
def is_anagram(s, t):    if len(s) != len(t):        return False    count = [0] * 26  # slot 0 = 'a' ... slot 25 = 'z'    for i in range(len(s)):        count[ord(s[i]) - ord("a")] += 1        count[ord(t[i]) - ord("a")] -= 1    return all(c == 0 for c in count)

The map and the array are the same idea. The array is a little faster in practice (no hashing) and its size never changes. The map works for any characters, including capital letters, digits, accents or emoji, which is LeetCode’s follow-up question.

The code, line by line

Here is the hash map version again:

Count with a hash map

function isAnagram(s, t) {  if (s.length !== t.length) return false;  const count = new Map(); // letter -> how many s has that t hasn't used up  for (const ch of s) {    count.set(ch, (count.get(ch) ?? 0) + 1);  }  for (const ch of t) {    if (!count.get(ch)) return false; // t has a letter s ran out of    count.set(ch, count.get(ch) - 1);  }  return true;}
def is_anagram(s, t):    if len(s) != len(t):        return False    count = {}  # letter -> how many s has that t hasn't used up    for ch in s:        count[ch] = count.get(ch, 0) + 1    for ch in t:        if count.get(ch, 0) == 0:            return False  # t has a letter s ran out of        count[ch] -= 1    return True

JavaScript fits an if and its return on one line, while Python uses two, so the line numbers sometimes differ. Where they do, we give both.

  • Line 1: define the function. (LeetCode writes var isAnagram = function(s, t) in JavaScript and def isAnagram(self, s, t) inside class Solution in Python.)
  • Line 2 (JS) / lines 2–3 (Python): different lengths can never be anagrams. Checking this first also makes the shortcut at the end safe.
  • Line 3 (JS) / line 4 (Python): an empty map. new Map() in JS, {} in Python.
  • Lines 4–5 (JS) / lines 5–6 (Python): count every letter of s. count.get(ch) ?? 0 (JS) and count.get(ch, 0) (Python) mean “the current count, or 0 if this letter isn’t in the map yet”. Then we store that plus 1.
  • Line 7: walk through t.
  • Line 8 (JS) / lines 8–9 (Python): if the count is 0 or missing, s has no spare copy of this letter. In JavaScript !count.get(ch) is true for both undefined (missing) and 0.
  • Line 9 (JS) / line 10 (Python): use one copy up.
  • Line 11: every letter of t was matched. Return true.

Dry run

Let’s trace s = "aab", t = "aba" with the hash map version.

phaseletterwhat happenscount afterwards
walk saa: 0 → 1{a: 1}
walk saa: 1 → 2{a: 2}
walk sbb: 0 → 1{a: 2, b: 1}
walk taa > 0, so a: 2 → 1{a: 1, b: 1}
walk tbb > 0, so b: 1 → 0{a: 1, b: 0}
walk taa > 0, so a: 1 → 0{a: 0, b: 0}
endevery count is 0: return true{a: 0, b: 0}
s = "aab", t = "aba"

Compare with t = "abb": at the third letter of t we’d need a b, but its count is already 0, so we’d return false right there.

Complexity

Brute force: cross letters off

Time

O(n²)

For each of the n letters of s we may scan all n letters of t.

Space

O(n)

A copy of t's letters so we can cross them off.

Sort and compare

Time

O(n log n)

Sorting each word dominates; the final comparison is n steps.

Space

O(n)

The sorted copies of both words.

Count with a hash map

Time

O(n)

One walk through s and one through t, with about one step per map update.

Space

O(1)

At most 26 keys (lowercase letters), however long the words are. With arbitrary characters it would be O(k) for k different characters.

Array of 26 slots

Time

O(n)

One walk through both words, then 26 checks.

Space

O(1)

Always exactly 26 counters.

Common mistakes and edge cases

What to say out loud, in this order:

  1. Clarify the alphabet: “Only lowercase a–z? Unicode?” The answer picks between the array and the map.
  2. Sorting first: “Sort both and compare: O(n log n).”
  3. Then counting: “Count with a map or a 26-slot array: O(n) time, O(1) space for a fixed alphabet.”
  4. Mention the length check and why it matters.

Likely follow-up questions:

  • “What if the inputs contain Unicode characters?” Use the hash map, not the 26-slot array.
  • “What if s is huge and streamed?” Counting works in one pass; sorting needs everything in memory.

Related problems:

  • Group Anagrams (this week): many words at once, grouped by their letters.
  • Top K Frequent Elements (this week): frequency counting again, then picking the biggest counts.
  • Contains Duplicate (this week): “seen or not” instead of “how many”.
  • Permutation in String (week 2): the same counts, inside a sliding window.