Самая длинная подстрока, содержащая ровно K гласных

Опубликовано: 20 Сентября, 2022

Дана строка str , содержащая как прописные, так и строчные буквы, и целое число K . Задача состоит в том, чтобы найти самую длинную подстроку, содержащую ровно K гласных (возможно, повторяющихся).

Примеры:

Input: GeeksForGeeks, K = 2
Output: 7, eksForG
Explanation: The longest substring having exactly two vowels is “eksForG”.

Input: TrueGeek, K = 3
Output: 6, TrueGe

Подход : Задачу можно решить, отслеживая количество гласных, встречающихся в текущем окне.
Выполните следующие шаги, чтобы решить проблему:

  • Создайте переменную « vow », чтобы отслеживать количество гласных в текущем окне.
  • Начните увеличивать размер окна. Если vow станет больше , чем K , начните сжимать окно спереди.
  • Максимизируйте размер окна на каждом шаге

Ниже приведена реализация вышеуказанного подхода:


Временная сложность : O(N)
Вспомогательное пространство : O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ