Valid Anagram

Examples

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

Both strings contain the same seven letters with the same counts, just rearranged.

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

The letters don't match - "car" has a c, and "rat" doesn't.

Input: s = "a", t = "ab"
Output: false

Different lengths can never be anagrams of each other.

Constraints

• 1 <= s.length, t.length <= 5 * 10^4

• s and t consist of lowercase English letters.

Approach

Two strings are anagrams exactly when they contain the same letters the same number of times. One straightforward way to check that is to rearrange (sort) both strings alphabetically - if they're anagrams, the sorted versions will be identical, character for character.

A faster way avoids sorting entirely: count how many times each letter appears in the first string, then walk through the second string subtracting from those counts as you go. If every count lands back at exactly zero by the end, the strings are anagrams.

Solutions

Brute Force - Sort and Compare

If two strings are anagrams, sorting each one's letters alphabetically must produce the exact same string. So sort both strings and compare the results directly.

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

  const sSorted = s.split("").sort().join("");
  const tSorted = t.split("").sort().join("");

  return sSorted === tSorted;
}

Time: O(n log n) · Space: O(n)

Optimal - Character Count

Count how often each letter appears in s using a hash map. Then scan through t, decreasing the count for each letter it contains. If t ever asks for a letter that isn't available, or in a different amount, the strings aren't anagrams.

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

  const counts = new Map();

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

  for (const ch of t) {
    if (!counts.has(ch) || counts.get(ch) === 0) {
      return false;
    }
    counts.set(ch, counts.get(ch) - 1);
  }

  return true;
}

Time: O(n) · Space: O(1) - at most 26 lowercase letters, so the map's size is bounded by a constant