242. Valid Anagram

Two strings are anagrams when they use the exact same letters with the exact same multiplicities. Skip sorting — a single frequency count (one pass up for s, one pass down for t) decides it in linear time.

● EasyHash Map / CountingFrequencyTypeScript

PROBLEM What we're solving

Return true if t is an anagram of s — same letters, same counts, any order. s="anagram", t="nagaram" → true. s="rat", t="car" → false.

KEY IDEA Anagram ⇔ identical letter histograms

Insight → two strings are anagrams iff their letter-frequency maps are equal. Order is irrelevant; only how many of each character matters. Build one histogram from s, then "spend" it down with t— if you ever overspend or finish with leftovers, they're not anagrams.

RECIPE Count up, count down, check empty

0 · Quick reject. Different lengths ⇒ not anagrams. Return early.
1 · Tally s. For each char, count[c]++.
2 · Drain with t. For each char, count[c]--. If it ever goes below zero, t has a letter s lacks → false.
3 · Verify. Equal lengths + never negative ⇒ all counts are zero ⇒ true.

Classic confusion →with the length check up front, you don't even need a separate "all zero?" loop — equal lengths plus "never went negative" guarantees every count returns to zero. Many people add a redundant final scan; it's harmless but unnecessary.

COST Complexity & alternatives

Sort both, compare

O(n log n)

Simple, but sorting dominates.

Frequency count

O(n)

O(n) time; O(1) space for fixed alphabet.

Space note

If restricted to lowercase a–z, a fixed number[26] array gives O(1) space. For full Unicode, a Map is O(k) where k = distinct characters. The sorting approach is the easiest to say but the count is the one to code.

Pattern transfer → letter-frequency signatures power Group Anagrams (the count tuple is the bucket key), Find All Anagrams in a String (sliding-window counts), and Permutation in String.

RUN IT Tally up for s, drain down for t

s =t =

step 0 / 16

STARTLengths match (7). Phase 1: tally every letter of s.

1function isAnagram(s: string, t: string): boolean {
2▶  if (s.length !== t.length) return false;
3▶  const count = new Map<string, number>();
4 
5  for (const c of s) {           // tally s: +1
6    count.set(c, (count.get(c) ?? 0) + 1);
7  }
8  for (const c of t) {           // drain with t: -1
9    const n = (count.get(c) ?? 0) - 1;
10    if (n < 0) return false;     // t has a char s lacks
11    count.set(c, n);
12  }
13  return true;   // equal lengths + never negative => all zero
14}

s =anagram

t =nagaram

Letter counts

empty

+1 from s−1 from twent negative

slowfast

TYPESCRIPT The solution, annotated

isAnagram.ts
function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false;
  const count = new Map<string, number>();

  for (const c of s) {           // tally s: +1
    count.set(c, (count.get(c) ?? 0) + 1);
  }
  for (const c of t) {           // drain with t: -1
    const n = (count.get(c) ?? 0) - 1;
    if (n < 0) return false;     // t has a char s lacks
    count.set(c, n);
  }
  return true;   // equal lengths + never negative => all zero
}

Reading it block by block

Line 2 — cheap reject.Unequal lengths can't be anagrams; bail before doing any work. This is also what makes the final "all zero" check unnecessary.

Lines 5–7 — build the histogram. Count every character of s. The ?? 0 handles first-time keys.

Lines 8–12 — spend it. Each character of t decrements its count. Going negative means t uses a letter more often than s has it → not an anagram.

Line 13 — the guarantee. Same total length and never negative ⇒ every count is exactly zero. Anagram confirmed.

Complexity → O(n) time (two linear passes), O(k) space for k distinct chars — O(1) if the alphabet is fixed (e.g. a number[26]).

INTERVIEWFollow-ups they'll ask

"Unicode / emoji input?" Iterate by code point and use a Map instead of a 26-slot array; or normalize first.
"Case-insensitive / ignore spaces?" Lowercase and strip non-letters before counting.
"Group Anagrams next?" The frequency signature (or sorted string) becomes a hash-map key to bucket words.
"One array instead of a map?" Increment for s and decrement for t in the same 26-length array, then check all zero.

OPTIMAL Hash Map / Counting

isAnagram.ts
function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false;
  const count = new Map<string, number>();

  for (const c of s) {           // tally s: +1
    count.set(c, (count.get(c) ?? 0) + 1);
  }
  for (const c of t) {           // drain with t: -1
    const n = (count.get(c) ?? 0) - 1;
    if (n < 0) return false;     // t has a char s lacks
    count.set(c, n);
  }
  return true;   // equal lengths + never negative => all zero
}

Complexity → O(n) time (two linear passes), O(k) space for k distinct chars — O(1) if the alphabet is fixed (e.g. a number[26]).

ALT 1 Brute force — sort both and compare

O(n log n) time · O(n) space

Two strings are anagrams iff their sorted characters are identical, so sort each and check equality — the simplest correct idea before reaching for a frequency count.

approach-2.ts
function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false;
  const sortStr = (str: string): string => [...str].sort().join('');
  return sortStr(s) === sortStr(t);
}

Note → Correct and tiny, but the two sorts dominate at O(n log n) and allocate new arrays/strings (O(n) space). Counting letters with a histogram — +1 for s, −1 for t— decides it in a single linear pass.

MNEMONIC The one-liner

"Lengths match, then s adds and t subtracts — never dip below zero."

TRIGGERS When you see _ → reach for _

"same letters, any order"	frequency count map
compare two strings' makeup	+1 for one, −1 for other
fixed lowercase alphabet	number[26] → O(1) space
"group / find all anagrams"	count signature as a key

SKELETON The reusable shape

skeleton.ts
if (s.length !== t.length) return false;
const count = new Map<string, number>();
for (const c of s) count.set(c, (count.get(c) ?? 0) + 1);
for (const c of t) {
  const n = (count.get(c) ?? 0) - 1;
  if (n < 0) return false;
  count.set(c, n);
}
return true;

FLASHCARDS Tap to flip

Two strings are anagrams iff…

their letter-frequency maps are identical (order ignored).

tap to flip

1 / 6

Answer to reveal explanations. No penalty for retries.Score: 0 / 8

QUESTION 01

Optimal time complexity?

QUESTION 02

What is the very first check?

QUESTION 03

During the second pass, a count dropping below zero means:

QUESTION 04

For a fixed lowercase a–z alphabet, the space complexity can be:

QUESTION 05

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

QUESTION 06

Why might you prefer the count approach over sorting?

QUESTION 07

#242 · Valid AnagramDecide if two strings are anagrams with a single frequency count — one pass up for s, one pass down for t — in linear time.Which algorithmic approach does this primarily use?

QUESTION 08

#242 · Valid AnagramDecide if two strings are anagrams with a single frequency count — one pass up for s, one pass down for t — in linear time.Which implementation correctly solves it?

PROBLEM What we're solving

KEY IDEA Anagram ⇔ identical letter histograms

RECIPE Count up, count down, check empty

COST Complexity & alternatives

Space note

RUN IT Tally up for s, drain down for t

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Hash Map / Counting

ALT 1 Brute force — sort both and compare

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _