Поддерживайте счётчики нужных символов в окне и число покрытых требований. Окно подходит, когда все символы требуемого алфавита представлены хотя бы один раз.
Как мы поймём, что текущее окно (между двумя указателями) уже содержит все символы алфавита?
Поддерживайте счётчики нужных символов в окне и число покрытых требований. Окно подходит, когда все символы требуемого алфавита представлены хотя бы один раз.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Поддерживайте счётчики нужных символов в окне и число покрытых требований. Окно подходит, когда все символы требуемого алфавита представлены хотя бы один раз.
Пусть required — множество символов, covered — число тех, чей счётчик положителен. При добавлении нужного символа переход 0 → 1 увеличивает covered; при удалении переход 1 → 0 уменьшает.
Условие полноты — covered == len(required). Посторонние символы его не меняют. Если требуется определённая кратность, вместо множества храните нужные количества и отмечайте достижение каждого порога. Тогда проверка полноты выполняется за O(1) на шаг, без повторного перебора всего алфавита.