Максимальное количество подстрок, содержащих по крайней мере 1 гласную и 1 согласную
Для заданной строки S , состоящей только из строчных латинских букв длины N, задача состоит в том, чтобы найти количество подстрок, каждая из которых содержит хотя бы 1 гласную и 1 согласную.
Примеры:
Input: S = “happybirthday”
Output: 3
Explanation: S can be divided as “ha”, “ppybi”, “rthday”Input: S = “geeksforgeeks”
Output 5
Explanation: S can be divided as “ge“, “ek“, “sfo“, “rge”, “eks”
Подход: Чтобы решить проблему, следуйте следующей идее:
The idea is to apply the greedy approach, traverse the string, and every time we encounter 1 vowel and 1 consonant increase the count by 1 and reset the number of vowels and consonants to 0.
Выполните следующие шаги, чтобы решить проблему:
- Инициализировать переменную ans = 0 , haveVowels = false (в текущей строке есть гласные или нет), haveConsonants = false (в текущей строке есть согласные или нет)
- Путешествовать по строке по каждому символу
- Если текущий символ - гласные, сделайте haveVowels = true, иначе haveConsonants = true
- Всякий раз, когда оба верны, считайте, что текущий подсегмент является допустимой подстрокой, увеличьте an на 1 , сделайте haveVowels = false и haveConsonants = false.
Ниже приведена реализация описанного выше подхода.
Временная сложность: O(N)
Вспомогательное пространство: O(1)