# Valid Anagram

- **Canonical ID**: `valid-anagram`
- **Canonical URL**: https://dsacheatsheet.com/problems/valid-anagram
- **Difficulty**: easy
- **Patterns**: Arrays & Hashing
- **Version**: 1.0.0 (verified 2026-11-11T21:00:00Z)
- **Original Problem**: https://leetcode.com/problems/valid-anagram/

## 1. Core Invariant / The Trick

Two strings are anagrams iff they have equal length and identical character frequency histograms. Increment for `s` and decrement for `t` in one 26-slot array (or map) and verify all counts return to 0.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(1)`
- **Proof**: Fixed alphabet (26 lowercase letters) bounds auxiliary frequency array to O(1); time is linear in string length N.

## 3. Minimal Idiomatic Code

### Python
```python
def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    counts = [0] * 26
    for cs, ct in zip(s, t):
        counts[ord(cs) - 97] += 1
        counts[ord(ct) - 97] -= 1
    return all(c == 0 for c in counts)
```

### TypeScript
```typescript
export function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false;
  const counts = new Int32Array(26);
  for (let i = 0; i < s.length; i++) {
    counts[s.charCodeAt(i) - 97]++;
    counts[t.charCodeAt(i) - 97]--;
  }
  return counts.every((c) => c === 0);
}
```

### C++
```cpp
bool isAnagram(string s, string t) {
    if (s.size() != t.size()) return false;
    int counts[26] = {0};
    for (size_t i = 0; i < s.size(); ++i) {
        counts[s[i] - 'a']++;
        counts[t[i] - 'a']--;
    }
    for (int c : counts) if (c != 0) return false;
    return true;
}
```

### Java
```java
boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] counts = new int[26];
    for (int i = 0; i < s.length(); i++) {
        counts[s.charAt(i) - 'a']++;
        counts[t.charAt(i) - 'a']--;
    }
    for (int c : counts) if (c != 0) return false;
    return true;
}
```

### Go
```go
func isAnagram(s, t string) bool {
    if len(s) != len(t) { return false }
    var c [26]int
    for i := 0; i < len(s); i++ {
        c[s[i]-'a']++
        c[t[i]-'a']--
    }
    for _, v := range c { if v != 0 { return false } }
    return true
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Failing fast on `len(s) != len(t)` saves work.
- Unicode follow-ups require a hash map instead of a fixed 26-int array.

### Follow-ups
- Group Anagrams: map each string to its sorted signature or 26-tuple frequency key.