2062. Count Vowel Substrings of a String

Description

A substring is a contiguous (non-empty) sequence of characters within a string.

A vowel substring is a substring that only consists of vowels ('a', 'e', 'i', 'o', and 'u') and has all five vowels present in it.

Given a string word, return the number of vowel substrings in word.

 

Example 1:

Input: word = "aeiouu"
Output: 2
Explanation: The vowel substrings of word are as follows (underlined):
- "aeiouu"
- "aeiouu"

Example 2:

Input: word = "unicornarihan"
Output: 0
Explanation: Not all 5 vowels are present, so there are no vowel substrings.

Example 3:

Input: word = "cuaieuouac"
Output: 7
Explanation: The vowel substrings of word are as follows (underlined):
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"

 

Constraints:

• 1 <= word.length <= 100
• word consists of lowercase English letters only.

 

Solutions

Solution: Hash Table

• Time complexity: O(5n)
• Space complexity: O(5)

 

JavaScript

/**
 * @param {string} word
 * @return {number}
 */
const countVowelSubstrings = function (word) {
  const size = word.length;
  const vowelMap = new Map([
    ['a', -1],
    ['e', -1],
    ['i', -1],
    ['o', -1],
    ['u', -1],
  ]);
  let result = (left = 0);

  function startMinSubstrVowel() {
    let start = size;

    for (const index of vowelMap.values()) {
      if (index === -1) return -1;
      start = Math.min(index, start);
    }
    return start;
  }
  for (let index = 0; index < size; index++) {
    const char = word[index];

    if (!vowelMap.has(char)) {
      left = index + 1;
      continue;
    }
    vowelMap.set(char, index);
    const start = startMinSubstrVowel();
    const count = start - left + 1;

    if (count < 0) continue;
    result += count;
  }
  return result;
};