🅰️242. Valid Anagram

Easy | Grind 75 | August 21 Sunday, 2022

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Constraints:

• 1 <= s.length, t.length <= 5 * 104

• s and t consist of lowercase English letters.

Example 1

Input: s = "anagram", t = "nagaram"
Output:true

Example 2

Input: s = "rat", t = "car"
Output: false

SOLUTION

We will first count the frequency of characters in string s and check if the same frequency of characters exists in string t. To do this, we will first loop through every character in string s and store the character and their frequency in a dictionary(we will call this s_count). We will then iterate over all the characters in string t and check if the character exists in s_count. If the character does not exist in s_count, we know string t is not an anagram of string s. If the character does exist in s_count, we will subtract the frequency of the current character in s_count by 1. Additionally, when the frequency of a character gets to 0. we will delete that character from s_count indicating we can have no more of the character in string t. In the end, we will return True if the length of s_count is 0. A length of 0 indicates that every character in string t matches string s characters.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # dictionary to store character frequency in string s
        s_count = Counter()
        
        # count the characters
        for char in s: 
            s_count[char] += 1
        
        for char in t:
            # char in t but not in s
            if char not in s_count: 
                return False
            
            else: 
                # subtract the count of the current char in the dict
                s_count[char] -= 1
                
                # no more character in s string 
                if s_count[char] == 0: 
                    del s_count[char]
                
       
        return (len(s_count) == 0)
        

TIME AND SPACE COMPLEXITY

TIME: O(n) where n is the length of longest string. We need to iterate over every element of both strings. This mean we perform 2n operations so, our time is O(n).

SPACE: O(n) where n is the length of string s. We store every character of string s and their frequency in our dictionary.