LeetCode 242: Valid Anagram - All Solutions Explained

Problem Statement

The Valid Anagram problem (LeetCode 242) asks you to determine if two strings are anagrams of each other. 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.

Copy codeInput: s = "anagram", t = "nagaram"
Output: true

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

Solution 1: Frequency Counter (Best Solution)

Explanation of the Best Solution

This approach uses a fixed-size array to count character frequencies, providing optimal efficiency for lowercase English letters.

1. Check length mismatch: If lengths differ, immediately return false
2. Initialize counter array: Size 26 (for each lowercase letter)
3. Count characters:
4. Increment for characters in s
5. Decrement for characters in t
6. Verify zero counts: All array elements should be zero

Step-by-Step Example

For s = "anagram", t = "nagaram": 1. Lengths match (7) 2. After processing: - a: +3 -3 = 0 - n: +1 -1 = 0 - g: +1 -1 = 0 - r: +1 -1 = 0 - m: +1 -1 = 0 3. All counts zero → true

Python Code (Frequency Counter)

Copy codedef isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False

    counter = [0] * 26
    for i in range(len(s)):
        counter[ord(s[i]) - ord('a')] += 1
        counter[ord(t[i]) - ord('a')] -= 1

    return all(count == 0 for count in counter)

Complexity

• Time Complexity: O(n) - single pass through both strings
• Space Complexity: O(1) - fixed-size array (26 elements)

Why It's the Best

• Most efficient solution
• Minimal memory usage
• Simple and elegant
• Works perfectly for given constraints

Solution 2: Sorting Approach

Explanation

This straightforward solution sorts both strings and compares them:

1. Sort both strings: Convert to sorted lists of characters
2. Compare results: If identical, they're anagrams

Python Code (Sorting)

Copy codedef isAnagram(s: str, t: str) -> bool:
    return sorted(s) == sorted(t)

Complexity

• Time Complexity: O(n log n) - due to sorting
• Space Complexity: O(n) - space needed for sorting

Pros and Cons

• Pros: Extremely simple implementation
• Cons: Less efficient for large strings

Solution 3: Hash Map (Dictionary)

Explanation

This general solution works for any character set using a dictionary:

1. Check lengths: Different lengths → false
2. Initialize counts: Default dictionary
3. Count characters:
4. Increment for s
5. Decrement for t
6. Check all zeros: All counts should cancel out

Python Code (Hash Map)

Copy codefrom collections import defaultdict

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

    counts = defaultdict(int)
    for char in s:
        counts[char] += 1
    for char in t:
        counts[char] -= 1

    return all(v == 0 for v in counts.values())

Complexity

• Time Complexity: O(n) - two passes through strings
• Space Complexity: O(1) - limited by character set size

When to Use

• When dealing with Unicode characters
• When you need explicit character counting

Solution 4: Counter Class (Pythonic)

Explanation

This leverages Python's built-in collections.Counter:

1. Compare Counters: Directly compare character counts

Python Code (Counter)

Copy codefrom collections import Counter

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

Complexity

• Time Complexity: O(n) - Counter construction
• Space Complexity: O(1) - limited by character set

Pros and Cons

• Pros: Most Pythonic one-liner
• Cons: Hides implementation details (less ideal for interviews)

Edge Cases to Consider

• Empty strings (considered anagrams)
• Strings with same characters but different frequencies
• Strings with identical characters in different order
• Very large strings (5×10⁴ characters)
• Strings with single repeated character ("aaaaa" vs "aaaaa")

Final Thoughts

• Frequency Counter: Best for interviews and production
• Sorting: Good for small strings or quick implementation
• Hash Map: General solution for any character set
• Counter: Most Pythonic but interviewers may want manual implementation

For coding interviews, the frequency counter solution is strongly recommended as it demonstrates optimal algorithm design.