Valid Anagram
EasyArrays and hashing
Two strings are anagrams when one is a rearrangement of the other: the same letters, each used the same number of times.
Given two strings s and t, return true if t uses exactly the letters of s, each the same number of times, in any order, and false if it does not.
Examples
Input: s = "night", t = "thing" Output: true
Both use n, i, g, h and t once each.
Input: s = "hello", t = "hollo" Output: false
hello has an e, and hollo has a second o instead.
Constraints
1 ≤ s.length, t.length ≤ 5 × 10⁴sandtuse lowercase English letters only.
Stuck?
Hint 1
Strings of different lengths can never be anagrams. For the same length, what has to match is how many times each letter appears.
Hint 2
Count the letters of s up and the letters of t down, in an array of 26 or a Map. Every count must end at zero.
The idea
Order does not matter for an anagram, only how many times each letter appears. Count the letters of s, then spend those counts on the letters of t. If the lengths match and t never asks for a letter that has run out, every count reaches zero together.
Time O(n)Extra space O(1): 26 counts
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
Strings of different lengths cannot be anagrams. With equal lengths, a t that never uses a letter more often than s has to use up every count exactly, so the loop below only needs to catch a letter used too often.
function isAnagram(s, t) { if (s.length !== t.length) return false; const count = new Map(); for (const c of s) { count.set(c, (count.get(c) || 0) + 1); } for (const c of t) { if (!count.get(c)) return false; count.set(c, count.get(c) - 1); } return true;}The trap
Checking that each letter of s appears somewhere in t tests which letters are used, not how many times. With the lengths equal, strings without a repeated letter come out right. When one string repeats a letter that the other has once, every letter is still found, and the check says true.
function isAnagram(s, t) { if (s.length !== t.length) return false; for (const c of s) if (!t.includes(c)) return false; // checks which letters, not how many return true;}