Intuition

Count frequency of each

Approach

Create a map conting the frequency of one string. For the second string decrease by one each letter:

  • If the count of a given letter is < 0, returns false
  • If the letter does not yet exists in the map, returns false

Complexity

  • Time complexity: O(n)

  • Space complexity: O(n)

Code

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if len(s) != len(t):
            return False
        
        letters = {}
        for c in s:
            if c in letters:
                letters[c] += 1
            else:
                letters[c] = 1
        
        for c in t:
            if c in letters:
                letters[c] -= 1
                if letters[c] < 0:
                    return False
            else:
                return False
        
        return sum(letters.values()) == 0

But there’s a even shorter version:

class Solution(object):
    def isAnagram(self, s, t):
        return collections.Counter(s) == collections.Counter(t)