Valid Anagram

───✱*.｡:｡✱*.:｡✧*.｡✰*.:｡✧*.｡:｡*.｡✱ ───

Problem

• Given two strings s and t, return true if the two strings are anagrams of each other, otherwise return false.
• An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different.

Solution

• Naive solution would be to loop through the characters of the first string, and then check if the characters are in the second string.
  • However, this would be O(n^2).
• A better solution is to keep a set of the amount of characters in the first string, and then loop through the second string’s character and check if the frequencies are the same.
  • This would be O(n + m).

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # time complexity: O(n + m)
        # space complexity: O(1)
        if len(s) != len(t):
            return False
 
        freq = {}
 
        for char in s:
            freq[char] = freq.get(char, 0) + 1
 
        for char in t:
            if char not in freq:
                return False
 
            freq[char] = freq[char] - 1
 
            if freq[char] < 0:
                return False
 
        return True

───✱*.｡:｡✱*.:｡✧*.｡✰*.:｡✧*.｡:｡*.｡✱ ───