> ## Documentation Index
> Fetch the complete documentation index at: https://hanzla.dev/llms.txt
> Use this file to discover all available pages before exploring further.

# 02 valid anagram

# Valid Anagram

🔗 **NeetCode Problem**:\
[https://neetcode.io/problems/is-anagram/question?list=neetcode150](https://neetcode.io/problems/is-anagram/question?list=neetcode150)

🔗 **LeetCode Problem**:\
[https://leetcode.com/problems/valid-anagram/](https://leetcode.com/problems/valid-anagram/)

***

## Problem Statement

Given two strings `s` and `t`, return `true` if `t` is an **anagram** of `s`, and return `false` otherwise.

An **anagram** is a word formed by rearranging the letters of another word, using all the original letters exactly once.

***

## Approach 1: Sorting (Simple but Not Optimal)

### Idea

Sort both strings and compare them. If they're equal after sorting, they're anagrams.

### Pseudocode

* Sort string `s`
* Sort string `t`
* Compare if sorted strings are equal

### Time Complexity

* **O(n log n)** → Due to sorting

### Why it's not optimal?

Sorting takes extra time. For anagrams, we only need to count characters, not arrange them.

***

## Optimized Approach 1: Using Hash Map (Unordered Map)

### Idea

Count the frequency of each character in both strings using hash maps.\
If the frequency maps are identical, the strings are anagrams.

### Key Insight

We can compare character frequencies without rearranging.

### C++ Implementation

```cpp theme={null}
class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) 
            return false;
        
        unordered_map<char, int> counter_of_s;
        for (int i = 0; i < s.size(); i++) 
            counter_of_s[s[i]]++;
        
        unordered_map<char, int> counter_of_t;
        for (int i = 0; i < t.size(); i++) 
            counter_of_t[t[i]]++;
        
        if (counter_of_s == counter_of_t) 
            return true;
        
        return false;
    }
};
```

### Complexity Analysis

* **Time Complexity**: **O(n)** → Single pass through each string
* **Space Complexity**: **O(1)** → Max 26 characters (lowercase English letters)

***

## Optimized Approach 2: Using Frequency Array (Most Optimal)

### Idea

Use a fixed-size array of 26 (for lowercase English letters) to count frequencies.\
Increment for characters in `s`, decrement for characters in `t`.\
If any count goes negative, they're not anagrams.

### Key Insight

Since we only have 26 possible lowercase letters, an array is more efficient than a hash map.

### C++ Implementation

```cpp theme={null}
class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) 
            return false;
        
        vector<int> freq(26, 0);
        
        // Count characters in s
        for (char ch : s) 
            freq[ch - 'a']++;
        
        // Decrement for characters in t
        for (char ch : t) {
            freq[ch - 'a']--;
            if (freq[ch - 'a'] < 0) 
                return false;
        }
        
        return true;
    }
};
```

### Complexity Analysis

* **Time Complexity**: **O(n)** → Two passes through the strings
* **Space Complexity**: **O(1)** → Fixed array of 26 elements

***

## Comparison of Approaches

| Approach            | Time Complexity | Space Complexity | Pros                        | Cons                  |
| ------------------- | --------------- | ---------------- | --------------------------- | --------------------- |
| **Sorting**         | O(n log n)      | O(1)             | Simple                      | Slower                |
| **Hash Map**        | O(n)            | O(1)\*           | Flexible for any characters | More memory per hash  |
| **Frequency Array** | O(n)            | O(1)             | Most efficient              | Limited to 26 letters |

\*Space is technically O(k) where k is unique characters, but for English letters it's O(1).

***

## Why Frequency Array is Most Optimal

1. **Fixed size**: Only 26 possible letters
2. **No hashing overhead**: Direct array indexing is faster
3. **Early termination**: Can return false immediately if count goes negative
4. **Minimal memory**: Array of 26 integers vs hash map overhead

***

## Example Walkthrough

### Example 1: `s = "listen"`, `t = "silent"`

**Using Frequency Array:**

```
Initial: freq = [0, 0, ..., 0] (26 zeros)

Processing s = "listen":
freq[11]++ → 'l'
freq[8]++  → 'i'
freq[18]++ → 's'
freq[19]++ → 't'
freq[4]++  → 'e'
freq[13]++ → 'n'

Processing t = "silent":
freq[18]-- → 's' (freq[18] = 0) ✓
freq[8]--  → 'i' (freq[8] = 0) ✓
freq[11]-- → 'l' (freq[11] = 0) ✓
freq[4]--  → 'e' (freq[4] = 0) ✓
freq[13]-- → 'n' (freq[13] = 0) ✓
freq[19]-- → 't' (freq[19] = 0) ✓

All counts remain ≥ 0 → Return true
```

### Example 2: `s = "hello"`, `t = "world"`

```
s.size() = 5, t.size() = 5 (same length, continue)

Processing s = "hello":
freq[7]++  → 'h'
freq[4]++  → 'e'
freq[11]+= 2 → 'l' (appears twice)
freq[14]++ → 'o'

Processing t = "world":
freq[22]-- → 'w' (freq[22] = -1) ✗ Return false
```

No character 'w' in `s`, so it goes negative → Not an anagram!

## Key Takeaways

* **Avoid sorting for this problem** (O(n log n) is slower than needed)
* **Frequency array is optimal** (O(n) time, O(1) space)
* **Character counting approach**: Count occurrences, don't rearrange
* **Two-pass is efficient**: Simple increment/decrement operations
* **Early termination**: Return false immediately if a character doesn't match
* **Fixed alphabet**: For English letters, array is faster than hash map