Сигнал задачи
Когда применять
Повторяется проверка наличия, частоты или соответствия.
Что держать в голове
- Уметь вычислять обязательное дополнение для текущего значения.
- Уметь использовать множество или словарь без повторного перебора префикса.
Сложность
- Поиск, вставка и удаление ожидаемо O(1), в худшем случае O(n); память O(n).
Границы и ошибки
- Ожидаемая O(1) не является гарантией худшего случая; изменяемые ключи и несогласованные hash/equality нарушают поиск.