---
title: Valid Anagram
difficulty: Easy
category: Hash Table
leetcode_id: 242
revision_count: 1
last_revision: 2026-09-12
---

# Valid Anagram

> **LeetCode:** [#242](https://leetcode.com/problems/valid-anagram/)
> **Сложность:** Easy
> **Категория:** Hash Table

## Условие

Даны две строки `s` и `t`. Вернуть `true`, если `t` — анаграмма `s` (т.е. содержит те же символы в том же количестве), иначе `false`.

```
Input:  s = "anagram", t = "nagaram"  →  Output: true
Input:  s = "rat",    t = "car"       →  Output: false
Input:  s = "a",      t = "ab"        →  Output: false
```

## Ключевая идея

Анаграмма означает одинаковую частотную карту символов. Считаем символы первой строки в хэш-таблицу (или массив из 26 для lowercase), вычитаем по второй — все счётчики должны быть нулевыми.

## Оценка сложности

- **Время:** O(n) — один проход по каждой строке
- **Память:** O(1) — массив фиксированного размера 26 (только латиница), либо O(k) для хэш-таблицы, где k — количество уникальных символов

## Решение (Ruby)

```ruby
# @param {String} s
# @param {String} t
# @return {Boolean}
def is_anagram(s, t)
  return false if s.length != t.length

  counts = Array.new(26, 0)

  s.each_byte { |b| counts[b - 97] += 1 }
  t.each_byte { |b| counts[b - 97] -= 1 }

  counts.all?(&:zero?)
end
```

> **Почему `97`?** `'a'.ord == 97` — ASCII-смещение для приведения символа к индексу 0..25.

## Разбор на примере

```
s = "anagram", t = "nagaram"

counts = [0]*26

'a'(97): counts[0] += 1 → [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
'n'(110): counts[13] += 1 → [... 0,1,0,0,0,0,0,0,0,0,0,0,0]
'a'(97): counts[0] += 1 → [2,0,...
... после всей s: counts = [3,0,0,0,0,0,1(г),1(р),0,0,0,0,1(м),1(н),0,0,0,0,0,0,0,0,0,0,0,0]

вычитаем t:
'a'(97): counts[0] -= 1 → [2,...
... после всей t: все нули → true
```

```
s = "rat", t = "car"

s: counts = [1(а->a),0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1(r->17),0(с->18),0,0,0,0,1(t->19),0,0,0,0]
t: 'c' → counts[2] -= 1 → [-1,...
   'a' → counts[0] -= 1 → [0,0,-1,...
   'r' → counts[17] -= 1 → [0,0,-1,...,0,-1 = 0,...

не все нули → false
```

## Edge Cases

- **Разная длина**: немедленный `false` — если длины не совпадают, анаграмма невозможна.
- **Пустые строки**: обе пусты → `true` (частотный проход не даст разночтений).
- **Одна пустая, другая нет** → `false` (длины разные).
- **Unicode/мультибайт**: задача предполагает только латиницу. Для общего случая — Hash Table вместо массива.
- **Заглавные буквы**: в LeetCode используются только lowercase, но если бы были — потребуется нормализация (`downcase`).

## Типичные ошибки

1. ❌ **Не проверять длину первой**: если строки разной длины, можно сэкономить проход.
2. ❌ **Сортировка вместо счёта**: O(n log n) вместо O(n) — проходит, но хуже по скорости.
3. ❌ **Использовать Hash без default value**: при вычитании символа, которого нет в первой строке, получим `nil → ошибка`. Решение: `Hash.new(0)`.
4. ❌ **Массив на 26, но символ вне диапазона `a-z`**: для латиницы норм, для общего случая — Hash.

## Альтернативные подходы

| Подход | Время | Память | Комментарий |
|--------|-------|--------|-------------|
| Sorting | O(n log n) | O(1) in-place / O(n) | Сортируем обе строки, сравниваем. Интуитивно понятно, но медленнее |
| Hash Table (one map, +1 / -1) | O(n) | O(k) | Считаем +1 для s, -1 для t, в конце все zero? |
| **Array[26] (lowercase only)** | **O(n)** | **O(1)** | **финальное решение** — быстрее хэша за счёт прямой адресации |
| Unicode / counter (Counter/Hash) | O(n) | O(k) | Универсальное решение для любых символов |

## Заметки после повторения

_— Заполняется после каждой тренировки._