Developers

Valid Anagram

EasyHashing and countingAlso known as LeetCode 242

You get two strings s and t made of lowercase English letters. Return true if t is an anagram of s, and false otherwise. A string is an anagram of itself.

An anagram is a rearrangement of the same letters: every letter appears the same number of times in both strings, in any order.

Examples

Input s = "anagram", t = "nagaram"
Output true
Input s = "rat", t = "car"
Output false
Input s = "ab", t = "abb"
Output false
Different lengths can never be anagrams.

Constraints

  • 1 <= s.length, t.length <= 50,000
  • s and t use only the lowercase letters a to z

Stuck? Take one hint at a time

Common mistakes
  • Forgetting to compare the lengths first, so "ab" and "abb" look equal.
  • Checking that each letter of s appears somewhere in t, without checking how many times.
  • Using a set instead of counts, which treats "aab" and "abb" as the same.
  • Sorting only one of the two strings before comparing.
Questions an interviewer may ask next
  • The strings may contain any Unicode characters. What changes? (A hash map instead of 26 slots.)
  • Group a whole list of words into anagram families. (Use the sorted word, or the letter counts, as the key.)
  • Check whether t is an anagram of any substring of s. (A sliding window with the same tally.)
  • Check anagrams of a stream where letters arrive one at a time.