Problem

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 ofvowel substrings in word.

Examples

Example 1

1
2
3
4
5
Input: word = "aeiouu"
Output: 2
Explanation: The vowel substrings of word are as follows (underlined):
- "**_aeiou_** u"
- "**_aeiouu_** "

Example 2

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

Example 3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
Input: word = "cuaieuouac"
Output: 7
Explanation: The vowel substrings of word are as follows (underlined):
- "c** _uaieuo_** uac"
- "c** _uaieuou_** ac"
- "c** _uaieuoua_** c"
- "cu** _aieuo_** uac"
- "cu** _aieuou_** ac"
- "cu** _aieuoua_** c"
- "cua** _ieuoua_** c"

Constraints

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

Solution

Method 1 – Sliding Window with Vowel Set

Intuition

A substring is a vowel substring if it contains only vowels and all five vowels at least once. We can use a sliding window to check all substrings that consist only of vowels and count those that contain all five vowels.

Approach

  1. Define a set of vowels: {‘a’, ’e’, ‘i’, ‘o’, ‘u’}.
  2. For each starting index, expand the window to the right as long as the characters are vowels.
  3. Use a set to track which vowels are present in the current window.
  4. If the set contains all five vowels, increment the answer.
  5. Continue for all possible starting indices.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int countVowelSubstrings(string word) {
        int n = word.size(), ans = 0;
        auto isVowel = [](char c) {
            return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
        };
        for (int i = 0; i < n; ++i) {
            set<char> st;
            for (int j = i; j < n && isVowel(word[j]); ++j) {
                st.insert(word[j]);
                if (st.size() == 5) ++ans;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func countVowelSubstrings(word string) int {
    n := len(word)
    isVowel := func(c byte) bool {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'
    }
    ans := 0
    for i := 0; i < n; i++ {
        st := map[byte]bool{}
        for j := i; j < n && isVowel(word[j]); j++ {
            st[word[j]] = true
            if len(st) == 5 {
                ans++
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int countVowelSubstrings(String word) {
        int n = word.length(), ans = 0;
        for (int i = 0; i < n; i++) {
            Set<Character> st = new HashSet<>();
            for (int j = i; j < n && isVowel(word.charAt(j)); j++) {
                st.add(word.charAt(j));
                if (st.size() == 5) ans++;
            }
        }
        return ans;
    }
    private boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    fun countVowelSubstrings(word: String): Int {
        val n = word.length
        var ans = 0
        fun isVowel(c: Char) = c in "aeiou"
        for (i in 0 until n) {
            val st = mutableSetOf<Char>()
            for (j in i until n) {
                if (!isVowel(word[j])) break
                st.add(word[j])
                if (st.size == 5) ans++
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def countVowelSubstrings(self, word: str) -> int:
        vowels = {'a','e','i','o','u'}
        n = len(word)
        ans = 0
        for i in range(n):
            st = set()
            for j in range(i, n):
                if word[j] not in vowels:
                    break
                st.add(word[j])
                if len(st) == 5:
                    ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
impl Solution {
    pub fn count_vowel_substrings(word: String) -> i32 {
        let n = word.len();
        let w = word.as_bytes();
        let vowels = [b'a', b'e', b'i', b'o', b'u'];
        let mut ans = 0;
        for i in 0..n {
            let mut st = std::collections::HashSet::new();
            for j in i..n {
                if !vowels.contains(&w[j]) { break; }
                st.insert(w[j]);
                if st.len() == 5 { ans += 1; }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    countVowelSubstrings(word: string): number {
        const vowels = new Set(['a','e','i','o','u'])
        let ans = 0
        for (let i = 0; i < word.length; ++i) {
            const st = new Set<string>()
            for (let j = i; j < word.length; ++j) {
                if (!vowels.has(word[j])) break
                st.add(word[j])
                if (st.size === 5) ans++
            }
        }
        return ans
    }
}

Complexity

  • ⏰ Time complexity: O(n^2) where n is the length of the string, as we check all substrings.
  • 🧺 Space complexity: O(1) for the set and variables.