Найдите все подстроки, содержащие ровно K уникальных гласных.

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

Примеры:

Input:  str = “aeiou”, K = 2
Output: “ae”, “ei”, “io”, “ou”
Explanation: These are the substrings containing exactly 2 distinct vowels.

Input: str = “TrueGeek”, K = 3
Output: “”
Explanation: Though the string has more than 3 vowels but there is not three unique vowels.
So the answer is empty.

Input: str = “TrueGoik”, K = 3
Output: “TrueGo”, “rueGo”, “ueGo”, “eGoi”, “eGoik”

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

• Сначала сгенерируйте все подстроки, начиная с каждого индекса i в диапазоне от 0 до N.
• Затем для каждой подстроки:
  • Сохраните хеш-массив для хранения вхождений уникальных гласных.
  • Проверьте, является ли новый символ в подстроке гласным или нет.
  • Если это гласная, увеличьте ее появление в хэше и подсчитайте количество найденных различных гласных.
  • Теперь для каждой подстроки, если количество различных гласных равно K , выведите подстроку.
• Если для любого цикла найти подстроки, начинающиеся с i , количество различных гласных превышает K , или длина подстроки достигла длины строки, прерываем цикл и ищем подстроки, начинающиеся с i+1 .

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

Временная сложность: O(N ² )
Вспомогательное пространство: O(N ² ) для хранения результирующих подстрок