LeetCode 242: Valid Anagram Solution in Python – A Step-by-Step Guide

What Is LeetCode 242: Valid Anagram?

In LeetCode 242: Valid Anagram, you’re given two strings, s and t, and your task is to check if they’re anagrams of each other. This problem is a step beyond basic array checks like LeetCode 238: Product of Array Except Self, focusing on character frequency rather than numerical operations.

Problem Statement

• Input: Two strings, s and t.
• Output: A boolean—true if t is an anagram of s, false otherwise.
• Rules: Strings contain only lowercase letters; anagrams must have identical character counts.

Constraints

• String length: 1 to 5 * 10^4.
• Characters: Lowercase English letters only.

Examples

• Input: s = "anagram", t = "nagaram"
• Output: true (same letters, same counts).
• Input: s = "rat", t = "car"
• Output: false (different letters).
• Input: s = "a", t = "a"
• Output: true (single matching character).

Understanding the Problem: Anagram Validation

To solve LeetCode 242: Valid Anagram in Python, we need to confirm that two strings have the same characters with the same frequencies, regardless of order. A naive approach—generating all permutations of one string and checking against the other—is far too slow. Instead, we’ll use two efficient methods: 1. Best Solution (Hash Map): O(n) time, O(1) space—fast and clever. 2. Alternative Solution (Sorting): O(n log n) time, O(1) space—simple but slower.

Let’s start with the best solution.

Best Solution: Hash Map Approach

Why This Is the Best Solution

The hash map approach is the top choice for LeetCode 242 because it runs in O(n) time by tracking character frequencies in a single pass, using minimal extra space since the alphabet is fixed (26 lowercase letters). It’s efficient, scalable, and perfect for this problem.

How It Works

• Create a hash map to count characters in the first string s.
• Decrease counts for characters in the second string t.
• Check if all counts return to zero—indicating identical frequencies.

Step-by-Step Example

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

• Step 1: Build hash map for s:
• a: 3, n: 1, g: 1, r: 1, m: 1
• Step 2: Process t:
• n: Decrease to 0.
• a: Decrease from 3 to 2.
• g: Decrease to 0.
• a: Decrease to 1.
• r: Decrease to 0.
• a: Decrease to 0.
• m: Decrease to 0.
• Step 3: All counts are 0 → true.

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

• Step 1: Hash map for s:
• r: 1, a: 1, t: 1
• Step 2: Process t:
• c: Not in map, fail early (or count becomes negative).
• Step 3: Non-zero counts → false.

Code with Detailed Line-by-Line Explanation

Here’s the Python implementation using a hash map:

Copy codeclass Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # Step 1: Quick length check
        if len(s) != len(t):
            return False

        # Step 2: Initialize hash map for 26 letters
        char_count = {}

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

        # Step 4: Decrease counts for t
        for char in t:
            if char not in char_count:
                return False
            char_count[char] -= 1
            if char_count[char] == 0:
                del char_count[char]  # Clean up for efficiency

        # Step 5: Check if all counts are zero
        return len(char_count) == 0

• Time Complexity: O(n)—single pass through both strings.
• Space Complexity: O(1)—fixed 26 letters, constant space.

This solution’s speed and elegance make it a standout.

Alternative Solution: Sorting Approach

Why an Alternative Approach?

The sorting approach is a great alternative for LeetCode 242 because it’s intuitive and easy to implement. By sorting both strings and comparing them, we can quickly see if they’re anagrams. It’s less efficient than the hash map but perfect for beginners learning string manipulation.

How It Works

• Sort both strings.
• Compare the sorted strings—if they match, they’re anagrams.

Step-by-Step Example

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

• Step 1: Sort s: "anagram" → "aaagmnr"
• Step 2: Sort t: "nagaram" → "aaagmnr"
• Step 3: Compare: "aaagmnr" == "aaagmnr" → true.

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

• Step 1: Sort s: "rat" → "art"
• Step 2: Sort t: "car" → "acr"
• Step 3: Compare: "art" != "acr" → false.

Code for Sorting Approach

Copy codeclass Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # Step 1: Quick length check
        if len(s) != len(t):
            return False

        # Step 2: Sort both strings
        sorted_s = ''.join(sorted(s))
        sorted_t = ''.join(sorted(t))

        # Step 3: Compare sorted strings
        return sorted_s == sorted_t

• Time Complexity: O(n log n)—sorting dominates.
• Space Complexity: O(1)—sorting in-place or minimal extra space.

It’s simple but sacrifices speed for clarity.

Comparing the Two Solutions

• Best Solution (Hash Map):
• Pros: O(n) time, constant space, fast.
• Cons: Slightly more code to understand.
• Alternative Solution (Sorting):
• Pros: Short, intuitive, beginner-friendly.
• Cons: O(n log n) time, slower.

The hash map wins for performance.

Additional Examples and Edge Cases

Single Character

• Input: s = "a", t = "a"
• Output: true

Empty Strings

• Input: s = "", t = ""
• Output: true (assuming allowed, though constraints specify length ≥ 1)

Different Lengths

• Input: s = "ab", t = "abc"
• Output: false

Both solutions handle these cases smoothly.

Complexity Breakdown

• Hash Map:
• Time: O(n)—linear and quick.
• Space: O(1)—fixed alphabet size.
• Sorting:
• Time: O(n log n)—sorting overhead.
• Space: O(1)—minimal extra space.

Hash map takes the efficiency crown.

Key Takeaways for Beginners

• Anagrams: Same characters, same counts, different order.
• Hash Map: Perfect for frequency counting.
• Sorting: Easy but costly—good for learning.
• Python Tip: Dictionaries are your friends—see [Python Basics](/python/basics).

Final Thoughts: Shuffle and Check Like a Pro

LeetCode 242: Valid Anagram in Python is a fantastic intro to string problems. The hash map solution shines with O(n) speed, while sorting offers a straightforward alternative. Hungry for more? Try LeetCode 49: Group Anagrams or LeetCode 438: Find All Anagrams in a String. Ready to test your skills? Head to Solve LeetCode 242 on LeetCode and start anagram hunting today!