Максимальное количество подстрок, содержащих по крайней мере 1 гласную и 1 согласную

Опубликовано: 27 Февраля, 2023

Для заданной строки 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)

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