Скользящее окно
Самая длинная подстрока с не более чем k различными символами
Найти длину самой длинной подстроки с ограничением на число разных символов
Постановка задачи
Описание (LeetCode - 340. Longest Substring with At Most K Distinct Characters)
Дана строка s и целое число k. Нужно вернуть длину самой длинной подстроки,
которая содержит не более k различных символов.
Пример 1:
s = "eceba", k = 2
Результат:
3
Пояснение:
Самая длинная подходящая подстрока - "ece". Она содержит 2 различных символа:
e и c.
Пример 2:
s = "aa", k = 1
Результат:
2
Ограничения:
1 <= s.length <= 5 * 10⁴0 <= k <= 50
Решение
Нам нужно найти самую длинную подстроку, в которой количество разных символов не
превышает k. Наивное решение перебирает все подстроки и для каждой считает
множество символов. Это слишком медленно.
Скользящее окно здесь подходит естественно: мы расширяем правую границу, пока окно остается допустимым, а когда различных символов становится слишком много, сужаем окно слева.
Идея решения:
Будем хранить частоты символов внутри текущего окна [left..right].
Когда добавляем символ справа:
Перейдите на Premium, чтобы продолжить
Разблокируйте доступ к этой статье и всем остальным материалам с NowInterview Premium
Перейти на Premium