Valid Anagram

Problem

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.

Example 1:

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

Example 2:

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

Constraints:

1 <= s.length, t.length <= 5 * 10^4
s and t consist of lowercase English letters.

Solution

Approach: Character Frequency Count

The key insight is that two strings are anagrams if and only if they contain the same characters with the same frequencies. We can use a hash map (or Counter in Python) to count character frequencies in both strings and compare them.

Implementation

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        count = {}

        # Count characters in s
        for char in s:
            count[char] = count.get(char, 0) + 1

        # Subtract characters in t
        for char in t:
            if char not in count:
                return False
            count[char] -= 1
            if count[char] < 0:
                return False

        return True

Alternative (Using Counter):

from collections import Counter

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return Counter(s) == Counter(t)

Alternative (Sorting):

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)

Complexity Analysis

Time Complexity: O(n), where n is the length of the strings. We iterate through both strings once to build and compare frequency maps. The sorting approach would be O(n log n).
Space Complexity: O(1) for the hash map approach, since we’re only storing at most 26 characters (lowercase English letters). The sorting approach uses O(n) space for the sorted arrays.

Key Insights

Length Check First: If the strings have different lengths, they cannot be anagrams. This early return saves computation.
Hash Map for Frequencies: Using a hash map to count character frequencies is more efficient than sorting (O(n) vs O(n log n)).
Counter Simplicity: Python’s Counter from collections makes the solution very concise and readable.
Sorting Trade-off: While sorted(s) == sorted(t) is elegant and simple, it’s less efficient (O(n log n)) but acceptable for many use cases.
Space Optimization: The hash map approach technically uses O(1) space since the character set is fixed (26 lowercase letters), even though we use a hash map.