Valid Anagram

Problem:

• https://neetcode.io/problems/is-anagram
• https://leetcode.com/problems/valid-anagram/description/

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.

Example 1:
Input: s = "racecar", t = "carrace"
Output: true

Example 2:
Input: s = "jar", t = "jam"
Output: false

Description

While using a set might be sufficient if we only need to maintain a set of unique characters, this problem requires us to keep track of both the number of unique characters and their occurrences. There are several approaches to solving this problem, but these three solutions provide a great starting point for further exploration.

Logic

• Iterate through each index from 0 to size of s or t
  • if the strings s and t do not have the same size, then they are not anagrams.
  • count unique characters of string s and t
  • if the unique characters and number of unique characters are not the same, then they are not anagrams.

Solution 1

class Solution():
    @staticmethod
    def isAnagram(s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if len(s) != len(t):
            return False

        unique_letters_s = dict()
        unique_letters_t = dict()

        for i in range(len(s)):
            # get a character in the dictionary, if it does not exist return 0.
            unique_letters_s[s[i]] = unique_letters_s.get(s[i], 0) + 1
            unique_letters_t[t[i]] = unique_letters_t.get(t[i], 0) + 1

        return unique_letters_s == unique_letters_t

solution = Solution.isAnagram("aacc", "caaa")

Solution 2

class Solution():
    @staticmethod
    def isAnagram(s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        # Better optimal solution (only 1 dictionary is required.)
        if len(s) != len(t):
            return False

        char_count = {}

        for char in s:
            if char in char_count:
                char_count[char] += 1
            else:
                char_count[char] = 1

        for char in t:
            if char in char_count:
                char_count[char] -= 1
            else:
                return False

        for count in char_count.values():
            if count != 0:
                return False

        return True

Solution.isAnagram("aacc", "caaa")

Solution 3

class Solution():
    @staticmethod
    def isAnagram(s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if len(s) != len(t):
            return False

        char_count = {}

        for i in range(len(s)):
            s_char = s[i]
            t_char = t[i]

            if s_char not in char_count:
                char_count[s_char] = 0
            if t_char not in char_count:
                char_count[t_char] = 0

            char_count[s_char] += 1
            char_count[t_char] -= 1

        for count in char_count.values():
            if count != 0:
                return False

        return True

Solution.isAnagram("aacc", "caaa")