Сложность: 🟡 Средняя
ℹ️ Описание
Дана строка s и максимальный размер подстроки k.
Необходимо написать функцию, которая вернет максимальное количество глассных в любой из подстрок строки s размером k.
⚠️ Ограничения
— Длина строки от 1 до 100000
— Строка состоит только из латинских букв в нижнем регистре
— Размер подстроки находится в диапазоне от 1 до длины исходной строки s.
1️⃣ Пример
Входные данные
s = "abciiidef"
k = 3
Ответ
3
В исходной строке есть подстрока длиной 3 состоящая исключительно из гласных iii.
2️⃣ Пример
Входные данные
s = "aeiou"
k = 2
Ответ
2
Так как исходная строка состоит полностью из гласных, любая подстрока длиной 2 также будет состоять из гласных.
3️⃣ Пример
Входные данные
s = "leetcode"
k = 3
Ответ
2
В исходной строке есть несколько подстрок (`lee`/`eet`/`ode`), в любой из которых максимальное количество гласных равно 2.
✅ Решение
Данная задача является ярким представителем класса задач, которые решаются с помощью скользящего окна:
- Нам необходимо создать окно длиной k (исходно левая граница окна равна 0, а правая - `k-1`)
- Двигать наше окно увеличивая левый и правый индекс на 1 на каждом шаге
- Считать сколько гласных попадает в наше окно на каждом шаге
Также важно помнить, что для каждого нового окна нам не обязательно с нуля считать количество гласных, мы всегда сможем быстро рассчитать ответ исходя из количества гласных в предыдущем окне и изменения нового окна относительно предыдущего, то есть нам достаточно смотреть только на границы окна.
Посмотреть реализацию в блоге
#strings #medium