# LeetCode 242: Valid Anagram

## Problem Restatement

We are given two strings:

```text
s and t
```

We need to determine whether `t` is an anagram of `s`.

Two strings are anagrams if:

- They contain exactly the same characters
- Every character appears the same number of times

The order does not matter.

LeetCode examples include:

```text
Input:  s = "anagram", t = "nagaram"
Output: true
```

and:

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

The problem constraints use lowercase English letters. The follow-up asks how to handle Unicode characters. ([leetcode.com](https://leetcode.com/problems/valid-anagram/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Strings `s` and `t` |
| Output | `True` if they are anagrams, otherwise `False` |
| Character set | Lowercase English letters |
| Requirement | Same character frequencies |

Function shape:

```python
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        ...
```

## Examples

Example 1:

```text
s = "anagram"
t = "nagaram"
```

Character counts:

| Character | Count |
|---|---:|
| `a` | `3` |
| `n` | `1` |
| `g` | `1` |
| `r` | `1` |
| `m` | `1` |

Both strings contain exactly the same frequencies.

So the answer is:

```text
True
```

Example 2:

```text
s = "rat"
t = "car"
```

The character counts differ.

For example:

```text
'r' appears in s
'c' appears in t
```

So the answer is:

```text
False
```

## First Thought: Sort Both Strings

If two strings are anagrams, then sorting them should produce the same result.

Example:

```text
"anagram" -> "aaagmnr"
"nagaram" -> "aaagmnr"
```

So we can write:

```python
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)
```

This works and is very concise.

But sorting costs:

```text
O(n log n)
```

We can do better with counting.

## Key Insight

Anagrams are defined by character frequencies.

So instead of sorting, we count how many times each character appears.

If every character frequency matches, the strings are anagrams.

Otherwise, they are not.

## Frequency Counting

For:

```text
s = "anagram"
```

the counts are:

| Character | Frequency |
|---|---:|
| `a` | `3` |
| `n` | `1` |
| `g` | `1` |
| `r` | `1` |
| `m` | `1` |

For:

```text
t = "nagaram"
```

the counts are identical.

So the strings are anagrams.

## Algorithm

1. If the lengths differ, return `False`.
2. Count character frequencies in `s`.
3. Count character frequencies in `t`.
4. Compare the two frequency maps.

If they are equal, return `True`.

Otherwise, return `False`.

## Using One Hash Map

We can optimize slightly.

Instead of building two separate maps:

1. Increment counts using `s`
2. Decrement counts using `t`
3. At the end, every count must be zero

Example:

```text
s = "abc"
t = "bca"
```

Process `s`:

| Character | Count |
|---|---:|
| `a` | `1` |
| `b` | `1` |
| `c` | `1` |

Process `t`:

| Character | New Count |
|---|---:|
| `b` | `0` |
| `c` | `0` |
| `a` | `0` |

All counts become zero, so the strings are anagrams.

## Correctness

If two strings are anagrams, then every character appears the same number of times in both strings.

The algorithm increments counts for characters in `s` and decrements counts for characters in `t`.

For any character:

- Matching frequencies produce a final count of zero.
- Different frequencies produce a nonzero final count.

Therefore:

- If all counts are zero, the strings contain exactly the same character frequencies, so they are anagrams.
- If any count is nonzero, some character frequency differs, so they are not anagrams.

The length check is also necessary. Two strings of different lengths cannot have identical character frequencies.

Therefore, the algorithm returns `True` exactly when the strings are anagrams.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each character is processed once |
| Space | `O(1)` | At most 26 lowercase English letters |

If Unicode characters are allowed, the space complexity becomes:

```text
O(k)
```

where `k` is the number of distinct characters.

## Implementation

```python
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        count = {}

        for ch in s:
            count[ch] = count.get(ch, 0) + 1

        for ch in t:
            count[ch] = count.get(ch, 0) - 1

        for value in count.values():
            if value != 0:
                return False

        return True
```

## Code Explanation

First check lengths:

```python
if len(s) != len(t):
    return False
```

Different lengths immediately rule out anagrams.

Create the frequency map:

```python
count = {}
```

Count characters from `s`:

```python
for ch in s:
    count[ch] = count.get(ch, 0) + 1
```

Then subtract frequencies using `t`:

```python
for ch in t:
    count[ch] = count.get(ch, 0) - 1
```

Finally, verify every count became zero:

```python
for value in count.values():
    if value != 0:
        return False
```

If all counts are zero:

```python
return True
```

## Alternative: collections.Counter

Python provides a built-in frequency counter.

```python
from collections import Counter

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return Counter(s) == Counter(t)
```

This is concise and readable.

Internally, it uses the same counting idea.

## Unicode Follow-Up

If Unicode characters are allowed, fixed-size arrays for 26 letters no longer work.

Hash maps remain valid because they can store arbitrary characters.

So the counting approach still works naturally for Unicode strings.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.isAnagram("anagram", "nagaram") is True
    assert s.isAnagram("rat", "car") is False
    assert s.isAnagram("", "") is True
    assert s.isAnagram("a", "a") is True
    assert s.isAnagram("ab", "ba") is True
    assert s.isAnagram("aacc", "ccac") is False
    assert s.isAnagram("listen", "silent") is True

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `"anagram"` vs `"nagaram"` | Standard valid example |
| `"rat"` vs `"car"` | Different characters |
| Empty strings | Minimum boundary |
| Single character | Small valid case |
| `"ab"` vs `"ba"` | Different order |
| `"aacc"` vs `"ccac"` | Frequency mismatch |
| `"listen"` vs `"silent"` | Common anagram pair |