Valid Anagram

The problem

Given two strings `s` and `t`, return whether `t` is a rearrangement of `s` using exactly the same letters the same number of times. "anagram" and "nagaram" are anagrams; "rat" and "car" are not.

The quick instinct is to sort both strings and compare, which is correct but costs O(n log n). If the two differ in length they can't possibly match, so that's the cheap first check.

The approach

Count how often each character appears in `s` by building a map from character to frequency. That map is the exact 'budget' of letters `t` is allowed to spend.

Walk through `t` and decrement the count for each character. If a character isn't in the map, or its count would go negative, `t` has a letter `s` doesn't — return false. I delete a key once it hits zero, so a perfect anagram drains the map to empty, and the final check is simply whether nothing is left.

The solution

function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false;
  const counts = new Map<string, number>();
  for (const ch of s) counts.set(ch, (counts.get(ch) ?? 0) + 1);
  for (const ch of t) {
    const n = counts.get(ch);
    if (n === undefined) return false;
    if (n === 1) counts.delete(ch);
    else counts.set(ch, n - 1);
  }
  return counts.size === 0;
}

Time O(n)Space O(n)