Marauder Bot

Problem

You are given two strings. Determine whether the second is an anagram of the first, meaning it uses exactly the same letters the same number of times, just possibly in a different order.

Example. For "listen" and "silent" the answer is true, since rearranging the letters of one produces the other. For "rat" and "car" the answer is false, even though both use three letters.

Key idea

Generating every rearrangement of one string and checking whether it matches the other is wildly impractical. A cleaner approach is to sort both strings and compare the results: two strings are anagrams exactly when their sorted forms are identical, which works but costs O(n log n).

A faster route counts letters instead of sorting. If the two strings have different lengths, they cannot be anagrams, so that check is free. Otherwise, walk the first string and increment a counter for each character; walk the second string and decrement the same counters. If every counter lands back at zero, the letter multisets match and the strings are anagrams. Using a fixed-size array indexed by letter, rather than a general hash map, keeps the constant factor small when the alphabet is known to be limited, such as lowercase English letters.

Solution

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

  const counts = new Array<number>(26).fill(0); // one slot per lowercase letter
  const base = 'a'.charCodeAt(0);

  for (let i = 0; i < s.length; i++) {
    counts[s.charCodeAt(i) - base]++; // increment for s
    counts[t.charCodeAt(i) - base]--; // decrement for t
  }

  return counts.every((count) => count === 0); // every letter balanced means matching counts
}

Complexity

Time: O(n). One pass to increment, one to decrement, both linear in string length.
Space: O(1). A fixed-size count array over a bounded alphabet, or O(n) with a general hash map for arbitrary characters.

Watch out for

Reject mismatched lengths immediately; there is no need to count anything once lengths differ.
A general hash map is required if the input is not restricted to a small known alphabet, such as full Unicode text.
Decide upfront whether the comparison should be case-sensitive; do not silently normalize case unless the problem calls for it.

Pattern

This is the character-frequency-counting pattern: reduce a string to a count signature and compare signatures instead of contents. It reappears in grouping anagrams, permutation-in-string, and substring problems built around matching character counts.

Valid Anagram