Valid Anagram

Easy#242counting

You get two words, s and t. Find out whether the letters of s can be rearranged to make t. Our example: "secure" and "rescue" — yes, both have the same letters, two e's included.

242 Valid AnagramWalkthrough · 1×

Example: s = "secure", t = "rescue". Under the words is the map: letter and its count.

stsecurerescuecount—
not reached yetcurrent lettercountedcount is 0below 0anagram

Both words have 6 letters: the lengths match

01/33
restart · back · play · step
Speed
1function isAnagram(s, t):
2 if len(s) != len(t):
3 return false
4 count = empty map // missing keys: 0
5 for each c in s:
6 count[c] = count[c] + 1
7 for each c in t:
8 count[c] = count[c] - 1
9 if count[c] < 0:
10 return false
11 return true
state
count
–
c
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Anagrams have the same letters the same number of times, only in a different order. So compare counts, not positions.
  2. s adds one for each of its letters, t takes one away. A count below 0 means t has that letter more times than s: false at once.
  3. The lengths are equal, so if nothing went below 0, nothing is left above 0 either: every count is 0, and the answer is true.

Complexity

Time O(n): one pass over each word. Memory O(1): at most 26 counts for lowercase letters, however long the words.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.