# Valid Anagram

[link](https://leetcode.com/problems/valid-anagram/) · Easy · `string`, `hash map`, `counting`, `sorting`

> "same elements, any order" → compare frequency counts instead of sorting. Small fixed alphabet (e.g. 26 lowercase letters) → use an array of size 26 for O(1) space; otherwise use a dict / Counter.

## Problem

> Given two strings `s` and `t`, return `true` if they are anagrams of each other,
> otherwise return `false`. Two strings are anagrams if they contain the same
> characters, each appearing the same number of times, in any order.

**Example 1**
```
Input:  s = "racecar", t = "carrace"
Output: true
```

**Example 2**
```
Input:  s = "jar", t = "jam"
Output: false
```

**Example 3**
```
Input:  s = "x", t = "x"
Output: true
```

**Constraints**
- `1 <= len(s), len(t) <= 5 * 10^4`
- `s` and `t` consist of lowercase English letters.

## Thinking

- **Brute force idea:** sort both strings and compare → $O(n \log n)$. Correct, but sorting
  does more work than needed: we only care *how many* of each letter, not their order.
- **Key insight:** two strings are anagrams ⇔ they have the **same character counts**.
  Counting is a single $O(n)$ pass. And since there are only 26 lowercase letters,
  the counts fit in a fixed-size array → $O(1)$ extra space.
- **Quick reject:** if `len(s) != len(t)`, they can't be anagrams.
- **Edge cases to remember:** different lengths, same letters but different counts
  (`"aab"` vs `"abb"`), single character, identical strings.

## Solution

### Approach A — my first solution (sort and compare)
**Complexity:** Time $O(n \log n)$ · Space $O(n)$ (`sorted` builds a new list of characters)

Short and correct. The cost is the sort: it puts every character in order, which is more than
the question needs.

```python
def is_anagram_sort(s: str, t: str) -> bool:
    return sorted(s) == sorted(t)
```

### Approach B — `Counter` (Pythonic)
`collections.Counter` builds a dict of *character → count*; two Counters are equal when every count matches.

**Complexity:** Time $O(n)$ · Space $O(k)$, where $k$ is the number of distinct characters (≤ 26 here).
Works for any characters, including Unicode.

```python
from collections import Counter

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

### Approach C — fixed array of 26 counts ✅ best practice (what interviewers expect)
Add 1 for each letter of `s`, subtract 1 for each letter of `t`. They're anagrams if every count ends at 0.
`ord(c) - ord('a')` maps `'a'..'z'` to `0..25`.

**Complexity:** Time $O(n)$ · Space $O(1)$ (always 26 integers, no matter how long the strings are).

```python
def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    count = [0] * 26
    for a, b in zip(s, t):
        count[ord(a) - ord("a")] += 1
        count[ord(b) - ord("a")] -= 1
    return all(c == 0 for c in count)
```

## Scratch / Experiments

Timing at the maximum input size ($5 \cdot 10^4$ characters).

Big-O isn't the whole story in Python: `sorted` and `Counter` do their work in C,
while Approach C's loop runs in Python, so C can be slower in wall-clock time even though
it's the better algorithm. In an interview, C is the answer to explain; in real Python code,
`Counter` is the idiomatic choice.

```python
import random, string

s = "".join(random.choices(string.ascii_lowercase, k=50_000))
t = "".join(random.sample(s, len(s)))  # a shuffled copy, so it's an anagram
%timeit is_anagram_sort(s, t)
%timeit is_anagram_counter(s, t)
%timeit is_anagram(s, t)
```

## Takeaways

- **Pattern:** "same elements, any order" → **compare frequency counts** instead of sorting.
  Small fixed alphabet (e.g. 26 lowercase letters) → use an **array of size 26** for $O(1)$ space;
  otherwise use a dict / `Counter`.
- **Mistakes I made:** reached for sorting, which is $O(n \log n)$, when counting is $O(n)$.
  Also skipped the cheap `len(s) != len(t)` early exit.
- **Related problems:** Contains Duplicate (#217, hash set), Group Anagrams (#49, use the sorted
  string or a 26-count tuple as a dict key), Find All Anagrams in a String (#438, sliding window +
  counts), Ransom Note (#383, counts).

---

From https://taosu.blog/notes/0242-valid-anagram