Problem Statement

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.

Additional information

• assume that the strings will contain at most 50,000 characters.
• The strings consist of lowercase English letters.
• The function should handle edge cases such as empty strings and strings of different lengths.

Example 1:

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

Output: true

Example 2:

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

Output: false

Sorting

Intuition

If two strings are anagrams, they must contain the exact same characters in the same frequencies. Therefore, if we sort both strings, they should be identical. This is the simplest approach but not the most efficient due to the cost of sorting.

Algorithm

1. Check if the lengths of the two strings are different. If so, return False.
2. Sort the characters of string s.
3. Sort the characters of string t.
4. Compare the sorted versions. If they are equal, return True; otherwise, return False.

def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    return sorted(s) == sorted(t)

Time & Space Complexity

• Time complexity: O(n log n)
• Reason: The dominant operation is the sorting algorithm.
• Space complexity: O(1) or O(n)
• Reason: Depends on the sorting implementation (e.g., Python's Timsort uses O(n) space).

Hash Map

Intuition

A more efficient approach is to count the frequency of each character in both strings. If the counts for every character match, the strings are anagrams. We can use two hash maps to store these counts and compare them.

Algorithm

1. First, check if the lengths of s and t are different. If they are, return False.
2. Initialize two hash maps, count_s and count_t.
3. Iterate through the strings and update the counts for each character.
4. Compare the two hash maps. If they are identical, return True.

def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False

    count_s, count_t = {}, {}

    for i in range(len(s)):
        count_s[s[i]] = count_s.get(s[i], 0) + 1
        count_t[t[i]] = count_t.get(t[i], 0) + 1
        
    return count_s == count_t

Time & Space Complexity

• Time complexity: O(n)
• Reason: We iterate through the strings once to count characters.
• Space complexity: O(1)
• Reason: The map size is limited to 26 lowercase English letters, which is constant space.