---
id: 242
title: Valid Anagram
difficulty: Easy
tags:
  - hash-table
  - string
  - sorting
status: Solved
date_solved: 2026-06-05
leetcode_url: https://leetcode.com/problems/valid-anagram/
review_needed: false
---

# 242. Valid Anagram

> [!info] **Problem Link**: [LeetCode - Valid Anagram](https://leetcode.com/problems/valid-anagram/)

## 📝 Problem Description

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`

---

## 💡 Approaches & Explanations

### Approach 1: Hash Map (Frequency Counter) — *Optimal*
Since an anagram must have the exact same characters with the same frequencies, we can use a hash map (or a fixed-size array for lowercase English letters) to count the occurrences of each character in both strings.
1. If the lengths of `s` and `t` are different, they cannot be anagrams.
2. Count the frequency of each character in `s`.
3. Decrement the frequency for each character in `t`.
4. If all counts return to zero, the strings are anagrams.

#### 📊 Complexity Analysis
- **Time Complexity:** $\mathcal{O}(N)$ where $N$ is the length of the strings. We iterate through each string once.
- **Space Complexity:** $\mathcal{O}(1)$ because the size of the hash map is limited by the number of unique characters in the alphabet (e.g., 26 for lowercase English letters).

---

### Approach 2: Sorting
If we sort both strings, two anagrams will result in the same identical string.
- **Time Complexity:** $\mathcal{O}(N \log N)$ due to sorting.
- **Space Complexity:** $\mathcal{O}(1)$ or $\mathcal{O}(N)$ depending on whether the language allows in-place string sorting or requires converting the string to a list.

---

## 💻 Code Implementations

### Python3
```python
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        
        count = {}
        for char in s:
            count[char] = count.get(char, 0) + 1
        
        for char in t:
            if char not in count or count[char] == 0:
                return False
            count[char] -= 1
            
        return True

# Alternative using collections.Counter
from collections import Counter
class Solution2:
    def isAnagram(self, s: str, t: str) -> bool:
        return Counter(s) == Counter(t)
```

---

## 🧠 Key Takeaways & Lessons
- **Character Counting:** For problems involving permutations or character frequency, a hash map or an array of size 26 is often the most efficient tool.
- **Early Exit:** Always check for length differences first to save time in edge cases.
- **Sorting as a Normalization:** Sorting is a powerful way to "normalize" data to check for equivalence in different orderings, though it is often slightly less efficient than counting.