Количество подстрок, содержащих ровно 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)