Valid Anagram

Try It Yourself

Use the editor below to decide whether both strings contain exactly the same characters with exactly the same frequencies. Character order does not matter.

Submit your implementation when it passes the examples. Check different lengths early and make sure repeated letters are counted rather than merely detected.

Valid Anagram

easyFrequency Counter · Strings15 minLC 242

Problem

Given two lowercase strings s and t, return true when t is an anagram of s.

An anagram uses every character from the original string exactly once, but the order may change.

Example 1:

Input: s = "anagram", t = "nagaram"

Output: true

Example 2:

Input: s = "rat", t = "car"

Output: false

Constraints

1 ≤ s.length, t.length ≤ 50,000
Both strings contain lowercase English letters.

0 attempts

Solution

First reject strings with different lengths. Count every character in the first string, then scan the second string and consume one saved occurrence at a time.

If a required character has no remaining count, the strings cannot be anagrams. Matching lengths and a successful second pass mean every character was paired.

function isAnagram(s, t) {
  if (s.length !== t.length) return false;

  const counts = new Map();

  for (const character of s) {
    counts.set(character, (counts.get(character) ?? 0) + 1);
  }

  for (const character of t) {
    const remaining = counts.get(character) ?? 0;
    if (remaining === 0) return false;
    counts.set(character, remaining - 1);
  }

  return true;
}

Big O notation

Measure	Complexity	Explanation
Time	`O(n)`	Each character in both equal-length strings is processed once.
Auxiliary space	`O(k)`	The frequency map stores up to k distinct characters.