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

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

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

Примеры:

Input: str = “aeiou”, K = 2
Output: 4
Explanation: The substrings are “ae”, “ei”, “io”, “ou”.

Input: str = “TrueGeek”, K = 3
Output: 5
Explanation: All such possible substrings are:
“TrueGe”, “rueGe”, “ueGe”, “eGee”, “eGeek”.

Подход: Решение этой проблемы основано на жадном подходе. Сгенерируйте все подстроки и для каждой подстроки проверьте количество гласных. Выполните шаги, указанные ниже.

  • Сгенерируйте все подстроки. Для каждой подстроки сделайте следующее
    • Храните количество вхождений гласных .
    • Проверьте, является ли новый символ в подстроке гласным или нет.
    • Если это гласная, увеличить количество найденных гласных
    • Теперь для каждой подстроки, если количество гласных равно K , увеличьте окончательный счет.
  • Верните окончательный счет в качестве требуемого ответа в конце.

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


Временная сложность: O(N 2 ), где N — длина строки.
Вспомогательное пространство: O(1)

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