Задачи
July 30

Задача. Количество подстрок с гласными буквами

Подстрока — это непрерывная и н непустая последовательность символов в строке.

А подстрока гласных — это подстрока, состоящая только из гласных ('а', 'е', 'i', 'o' и 'u') и содержащая все пять гласных.

Необходимо вернуть количество подстрок гласных в заданном слове.

Пример:

word = "aeiouu"
Output: 2
Примечание: "aeiou", "aeiouu"

Разбор

Одно из наиболее простых решений - это использование хэш-таблицы. Алгоритм будет следующим:

  1. Все гласные буквы (их 5) добавим в хэш-таблицу Vowels.
  2. Частный случай: если строка меньше 5, очевидно, что все гласные не помещаются, возвращаем 0.
  3. Далее проходим по строке и ищем все подстроки, которые содержат 5 и более гласных и ни одной согласной.
  4. Так как мы ищем все возможные подстроки, то испольузуем вложенный цикл. 1й цикл проходит по всей строке, вложенный цикл идет от текущего символа и проверяет, что каждый след.символ это гласная.
  5. Внутри вложенного цикла 2я хэш-таблица считает все полученные гласные, если размер 2й хэш-таблицы больше или равен 5, увеличиваем результирующий счетчик.
  6. Не забываем обнулить 2ю хэш-таблицу в конце 1го цикла.
  7. Выводим результат.

Детали реализации смотрите ниже.

Реализация

Play-test

https://dotnetfiddle.net/nSFq8X