easy

Valid Anagram

Decide whether two words use exactly the same letters by counting the letters of one in a hash map and spending them on the other.

1. Define the problem

Valid Anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise. Two words are anagrams when they use exactly the same letters exactly the same number of times, only in a different order. Count every letter of s in a hash map from letter to how many times it appears, then walk through t and take one away for each letter you meet. If a letter is missing, or the two strings are different lengths, they cannot be anagrams.

Constraints

  • 1 ≤ s.length, t.length ≤ 5 × 104
  • s and t consist of lowercase English letters
  • The comparison is case sensitive

Example

Inputs = "anagram", t = "nagaram"
Outputtrue

Explanation Both words contain three a, one n, one g, one r and one m, so t is a rearrangement of s.

2. Know the words first

In plain terms

Anagram
A word made by rearranging all the letters of another word, using every letter the same number of times. "listen" and "silent" are anagrams.
Hash map
A lookup table that stores pairs of key and value. Here the key is a letter and the value is how many times that letter appeared. Looking a key up takes roughly the same tiny amount of time no matter how many keys are stored.
Counter
A hash map used to hold tallies. Every time you meet a letter you add one to its stored number.
3. Visualize the solution

One cell per letter key in the hash map, value = the tally

One cell per letter key in the hash map, value = the tally
Statusinit

Both words have 7 letters, so start an empty tally for every letter.

What happens in this step

s = "anagram", t = "nagaram"
s.length = 7 and t.length = 7, so they could still be anagrams

The hash map starts empty, shown here as a dash in every cell.
Different lengths would have ended the answer right here.
Step 1 of 6

Steps to visualize

  1. Each cell below is one key in the hash map: the letter is the label and its tally is the value.
  2. If the two strings have different lengths, stop straight away and answer false.
  3. Walk through s and add one to the tally of each letter you meet.
  4. Walk through t and take one away from each letter. A tally that is already zero means t has a letter s does not have.
  5. If you finish t without running out of any letter, the two words are anagrams.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One cell per letter key in the hash map, value = the tally
Statusinit

Both words have 7 letters, so start an empty tally for every letter.

What happens in this step

s = "anagram", t = "nagaram"
s.length = 7 and t.length = 7, so they could still be anagrams

The hash map starts empty, shown here as a dash in every cell.
Different lengths would have ended the answer right here.
Step 1 of 6
5. Solution

Solution

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

  const counts = new Map();

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

  for (const char of t) {
    const current = counts.get(char) || 0;

    if (current === 0) {
      return false;
    }

    counts.set(char, current - 1);
  }

  return true;
}
Time
O(n)
Space
O(1) because at most 26 letter keys are stored
6. Test cases

Test cases

InputExpectedCovers
s = "anagram", t = "nagaram"trueexample from the description
s = "rat", t = "car"falsesame length but different letters
s = "a", t = "ab"falselengths do not match, so the early exit runs
s = "a", t = "a"truesmallest possible input
s = "aacc", t = "ccac"falsesame letters but used a different number of times
s = "conversation", t = "conservation"truelonger pair of real words

Keep reading

TopicDescription
Hash TablesKey-to-value lookup in average O(1) via hashing into buckets.
Contains DuplicateAnswer whether any value repeats in an array by keeping every value seen so far in a hash set and stopping at the first repeat.
Ransom NoteCheck whether one string can be built from the letters of another by counting the available letters in a hash map and spending them.
First Unique Character in a StringFind the index of the first character that never repeats, using one pass to count every character and a second pass to find it.
Group AnagramsGroup words that are rearrangements of each other by filing every word in a hash map under the sorted letters that form its signature.
Valid SudokuCheck a sudoku board for repeated digits in any row, column or 3 by 3 box by storing one combined key per rule in a hash set.