Valid Anagram

The problem

Given two strings of lowercase letters, s and t, return true if t is an anagram of s: it uses exactly the same letters, each the same number of times, in any order. Otherwise return false. Two empty strings are anagrams of each other.

What to write

function solve(s: string, t: string): boolean

Input
s = "listen"
t = "silent"

Output
true

Input
s = "rat"
t = "car"

Output
false

Constraints

0–10,000 lowercase English letters per string.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Each string can hold 10,000 letters, so trying every rearrangement of one word is out of the question. Notice also that two words of different lengths can never be anagrams.

2. Hint 2: Ask a smaller question

   Imagine both words written on paper with the letters cut apart. What would you compare to decide? Does the order of the letters matter at all?

3. Hint 3: Name the pattern

   Only the number of each letter matters, not the order. So count the letters: build a table from each letter to how many times it appears. This is frequency counting. Read the lesson on frequency counting.

4. Hint 4: State the invariant

   Two words are anagrams exactly when every letter has the same count in both. While you use up the first word's counts with the second word's letters, no count may go below zero.

5. Hint 5: Sketch the pseudocode

   If the lengths differ, return false. Count each letter of the first word in a map. For each letter of the second word: if its count is missing or zero, return false; otherwise subtract one. Return true.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Count each letter of the first word, then use those counts up with the letters of the second. If a letter runs out, or the lengths differ, they are not anagrams.

The slow way

Sort the letters of both words and compare the results. It is correct and short, but sorting does more work than the question needs: about n log n steps, when one pass over each word is enough.

The insight

An anagram only moves letters around. So two words are anagrams exactly when each letter appears the same number of times in both, and counting letters takes one pass.

Step by step

1. Words of different lengths cannot be anagrams. An anagram uses every letter of the other word exactly once, so the two words must be the same length. Checking this first also makes the rest simpler.
2. Count how many times each letter appears in the first word. The table of counts is everything that matters about the first word. The order of its letters is thrown away on purpose.
3. The first word has none of this letter left: not an anagram. A count that is missing or already zero means the second word has more of this letter than the first one does.
4. Otherwise use up one of that letter. Each letter of the second word is paired with one copy of the same letter in the first, and that copy cannot be used again.
5. Every letter was matched one for one. The lengths are equal and no letter ran out, so each letter of the first word was used exactly once.

The same numbered steps are the comments in each solution.

function solve(s, t) {
  // 1. Words of different lengths cannot be anagrams
  if (s.length !== t.length) return false;
  // 2. Count how many times each letter appears in the first word
  const counts = new Map();
  for (const letter of s) counts.set(letter, (counts.get(letter) || 0) + 1);
  for (const letter of t) {
    // 3. The first word has none of this letter left: not an anagram
    const left = counts.get(letter);
    if (!left) return false;
    // 4. Otherwise use up one of that letter
    counts.set(letter, left - 1);
  }
  // 5. Every letter was matched one for one
  return true;
}

function solve(s: string, t: string): boolean {
  // 1. Words of different lengths cannot be anagrams
  if (s.length !== t.length) return false;
  // 2. Count how many times each letter appears in the first word
  const counts = new Map<string, number>();
  for (const letter of s) counts.set(letter, (counts.get(letter) || 0) + 1);
  for (const letter of t) {
    // 3. The first word has none of this letter left: not an anagram
    const left = counts.get(letter);
    if (!left) return false;
    // 4. Otherwise use up one of that letter
    counts.set(letter, left - 1);
  }
  // 5. Every letter was matched one for one
  return true;
}

def solve(s, t):
    # 1. Words of different lengths cannot be anagrams
    if len(s) != len(t):
        return False
    # 2. Count how many times each letter appears in the first word
    counts = {}
    for letter in s:
        counts[letter] = counts.get(letter, 0) + 1
    for letter in t:
        # 3. The first word has none of this letter left: not an anagram
        left = counts.get(letter, 0)
        if not left:
            return False
        # 4. Otherwise use up one of that letter
        counts[letter] = left - 1
    # 5. Every letter was matched one for one
    return True

Example 1, traced

Input
s = "listen"
t = "silent"

Output
true

Why it works

Each letter of the second word uses up one copy of the same letter in the first word, and the check stops as soon as a copy is missing. Because the two words have the same length, using a copy for every letter leaves no copy over. So the two words hold the same letters, the same number of times.

Time and space

Time O(n), extra space O(1): at most 26 counts. Each word is read once, so the time is O(n) for words of length n. The table never holds more than 26 letters however long the words are, so the extra space is constant.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Keep the length check. Without it, a second word that is only part of the first, such as "ab" against "abc", would pass.
• Check a letter's count before you subtract. A missing letter and a letter whose count has reached zero both mean the second word has one too many.

Pattern

Frequency counting. Builds on Contains Duplicate.

Keep going