Valid Anagram

The problem. Given two strings s and t of lowercase letters, return true if t is an anagram of s — the same letters, each used the same number of times, in any order.

Example

s = "listen", t = "silent"     ->  true
s = "anagram", t = "nagaram"   ->  true
s = "rat", t = "car"           ->  false   ("t" in one, "c" in the other)

The pattern: frequency counting

Many string questions don't care about order at all — only about how many of each character there are. Anagrams, "can you build the ransom note from the magazine", "find the first character that appears once", "group words with the same letters". The pattern: count the characters, then answer the question from the counts.

The counter is chosen by the alphabet, as the memory lesson showed. For lowercase English letters, an int[26] indexed by ch - 'a' is the fastest and smallest. For any characters at all, use a hash map from character to count. Either way, counting a string of length n is one pass: O(n).

1. Sort both and compare

Anagrams contain the same letters, so after sorting they are the same string.

1function isAnagram(s, t) {2  if (s.length !== t.length) return false;3  const sorted = (x) => [...x].sort().join("");4  return sorted(s) === sorted(t);             // anagrams sort to the same string5}

Time O(n log n), space O(n). Sorting dominates; the sorted copies take O(n) (C++ sorts the copies it was given).

2. Count with one array

Use a single array of 26 counters: every letter of s adds one, every letter of t takes one away. If the strings are anagrams, everything cancels and all 26 counters end at zero.

1function isAnagram(s, t) {2  if (s.length !== t.length) return false;   // different lengths can't match3  const count = new Array(26).fill(0);4  for (let i = 0; i < s.length; i++) {5    count[s.charCodeAt(i) - 97]++;            // s adds one6    count[t.charCodeAt(i) - 97]--;            // t takes one away7  }8  return count.every((c) => c === 0);         // every letter balanced out?9}

Time O(n), space O(1). One pass over both strings and a final check of 26 counters, which is constant however long the strings are.

Comparing the approaches

The classic follow-up: what if the strings contain any Unicode characters? Then 26 slots aren't enough — swap the array for a hash map from character to count. The algorithm doesn't change.

Edge cases to test

Variations